EC330 Applied Algorithms and Data Structures For Engineers Fall 2018 Homework 7
EC330 Applied Algorithms and Data Structures For Engineers Fall 2018 Homework 7
Fall 2018
Homework 7
This homework has a written part and a programming part. Both are due at 8:59 am on
November 30. You should submit both parts on Blackboard. For the written part, you
should submit a single PDF file containing either typeset answers or scanned copies of
hand-written answers. Make sure you write your answers clearly. For the programming
part, your code should be easy to read and understand, and demonstrate good code
design and style. Your program must compile and run on the lab computers.
a. Implement a trie-based map. A map stores data in the form of (key, value) pairs
where every key is unique and each key maps to a value. You can assume that the
keys are strings composed of lowercase letters only, and the values are positive
integers. Implement the insert, search, and remove methods in trie.h.
For example, below is the result trie after the sequence of insertion (“to”, 7),
(“tea”, 3), (“ten”, 12), (“in”, 5), (“inn”, 9). Note that the size of the resulting map
should be 5 and the size of the resulting tree should be 9.
1
You are encouraged to create your own main with test cases. Submit only the
modified trie.h file. [40 pt]
b. Imagine that you are managing a supercomputer that runs jobs for your clients. A
client can submit a set of computing jobs, numbered from 1 to n, and the
dependencies among them. The dependencies are expressed as pairs. For
example, (1, 2) means job 2 depends on job 1, i.e. job 2 can only start after job 1
finishes. Write a program that determines if it is possible to finish all the jobs
without actually running them. Below are some example inputs and their expected
outputs.
Implement the method canFinish in job.h. In the written part of your answer,
state and justify both the time and space complexity of your algorithm. Submit
both the modified job.h file and the written complexity analysis. [50 pt]