Description
Introduction Welcome to your first Programming Assignment in the Data Structures course of the Data Structures and Algorithms Specialization! In this programming assignment, you will be practicing implementing basic data structures and using them to solve algorithmic problems. In some of the problems, you just need to implement and use a data structure from the lectures, while in the others you will also need to invent an algorithm to solve the problem using some of the basic data structures. In this programming assignment, the grader will show you the input and output data if your solution fails on any of the tests. This is done to help you to get used to the algorithmic problems in general and get some experience debugging your programs while knowing exactly on which tests they fail. However, note that for very big inputs the grader cannot show them fully, so it will only show the beginning of the input for you to make sense of its size, and then it will be clipped. You will need to generate big inputs for yourself. For all the following programming assignments, the grader will show the input data only in case your solution fails on one of the first few tests (please review the questions 5.4 and 5.5 in the FAQ section for a more detailed explanation of this behavior of the grader).
Learning Outcomes Upon completing this programming assignment you will be able to: 1. Apply the basic data structures you’ve just studied to solve the given algorithmic problems. 2. Given a piece of code in an unknown programming language, check whether the brackets are used correctly in the code or not. 3. Implement a tree, read it from the input and compute its height. 4. Simulate processing of computer network packets.
Passing Criteria: 2 out of 3 Passing thisprogramming assignmentrequires passingat least2out of3code problemsfrom thisassignment. In turn, passing a code problem requires implementing a solution that passes all the tests for this problem in the grader and does so under the time and memory limits specified in the problem statement.
Contents 1 Problem: Check brackets in the code 3
1
2 Problem: Compute tree height 6
3 Advanced Problem: Network packet processing simulation 9
4 General Instructions and Recommendations on Solving Algorithmic Problems 12 4.1 Reading the Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Designing an Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Implementing Your Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.4 Compiling Your Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.5 Testing Your Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.6 Submitting Your Program to the Grading System . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.7 Debugging and Stress Testing Your Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5 Frequently Asked Questions 15 5.1 I submit the program, but nothing happens. Why? . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 I submit the solution only for one problem, but all the problems in the assignment are graded. Why? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.3 What are the possible grading outcomes, and how to read them? . . . . . . . . . . . . . . . . 15 5.4 How to understand why my program fails and to fix it? . . . . . . . . . . . . . . . . . . . . . 16 5.5 Why do you hide the test on which my program fails? . . . . . . . . . . . . . . . . . . . . . . 16 5.6 My solution does not pass the tests? May I post it in the forum and ask for a help? . . . . . . 17 5.7 My implementation always fails in the grader, though I already tested and stress tested it a lot. Would not it be better if you give me a solution to this problem or at least the test cases that you use? I will then be able to fix my code and will learn how to avoid making mistakes. Otherwise, I do not feel that I learn anything from solving this problem. I am just stuck. . . . 17
2
1 Problem: Check brackets in the code Problem Introduction In this problem you will implement a feature for a text editor to find errors in the usage of brackets in the code.
Problem Description Task. Your friend is making a text editor for programmers. He is currently working on a feature that will find errors in the usage of different types of brackets. Code can contain any brackets from the set []{}(), where the opening brackets are [,{, and ( and the closing brackets corresponding to them are ],}, and ). For convenience, the text editor should not only inform the user that there is an error in the usage of brackets, but also point to the exact place in the code with the problematic bracket. First priority is to find the first unmatched closing bracket which either doesn’t have an opening bracket before it, like ] in ](), or closes the wrong opening bracket, like } in ()[}. If there are no such mistakes, then it should find the first unmatched opening bracket without the corresponding closing bracket after it, like ( in {}([]. If there are no mistakes, text editor should inform the user that the usage of brackets is correct. Apart from the brackets, code can contain big and small latin letters, digits and punctuation marks. More formally, all brackets in the code should be divided into pairs of matching brackets, such that in each pair the opening bracket goes before the closing bracket, and for any two pairs of brackets either one of them is nested inside another one as in (foo[bar]) or they are separate as in f(a,b)-g[c]. The bracket [ corresponds to the bracket ], { corresponds to }, and ( corresponds to ). Input Format. Input contains one string S which consists of big and small latin letters, digits, punctuation marks and brackets from the set []{}(). Constraints. The length of S is at least 1 and at most 105. Output Format. Ifthecodein S usesbracketscorrectly,output“Success”(withoutthequotes).Otherwise, output the 1-based index of the first unmatched closing bracket, and if there are no unmatched closing brackets, output the 1-based index of the first unmatched opening bracket. Time Limits. C: 1 sec, C++: 1 sec, Java: 1 sec, Python: 1 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec. Memory Limit. 512MB. Sample 1. Input: [] Output: Success Explanation: The brackets are used correctly: there is just one pair of brackets [ and ], they correspond to each other, the left bracket [ goes before the right bracket ], and no two pairs of brackets intersect, because there is just one pair of brackets.
3
Sample 2. Input: {}[] Output: Success Explanation: The brackets are used correctly: there are two pairs of brackets — first pair of { and }, and second pair of [ and ] — and these pairs do not intersect. Sample 3. Input: [()] Output: Success Explanation: The brackets are used correctly: there are two pairs of brackets — first pair of [ and ], and second pair of ( and ) — and the second pair is nested inside the first pair. Sample 4. Input: (()) Output: Success Explanation: Pairs with the same types of brackets can also be nested. Sample 5. Input: {[]}() Output: Success Explanation: Here there are 3 pairs of brackets, one of them is nested into another one, and the third one is separate from the first two. Sample 6. Input: { Output: 1 Explanation: The code { doesn’t use brackets correctly, because brackets cannot be divided into pairs (there is just one bracket). There are no closing brackets, and the first unmatched opening bracket is {, and its position is 1, so we output 1.
4
Sample 7. Input: {[} Output: 3 Explanation: The bracket } is unmatched, because the last unmatched opening bracket before it is [ and not {. It is the first unmatched closing bracket, and our first priority is to output the first unmatched closing bracket, and its position is 3, so we output 3. Sample 8. Input: foo(bar); Output: Success Explanation: All the brackets are matching, and all the other symbols can be ignored. Sample 9. Input: foo(bar[i); Output: 10 Explanation: ) doesn’t match [, so ) is the first unmatched closing bracket, so we output its position, which is 10.
Starter Files There are starter solutions only for C++, Java and Python3, and if you use other languages, you need to implement solution from scratch. Starter solutions read the code from the input and go through the code character-by-character and provide convenience methods. You need to implement the processing of the brackets to find the answer to the problem and to output the answer.
What to Do To solve this problem, you can slightly modify the IsBalanced algorithm from the lectures to account not only for the brackets, but also for other characters in the code, and return not just whether the code uses brackets correctly, but also what is the first position where the code becomes broken.
Need Help? Ask a question or see the questions asked by other learners at this forum thread.
5
2 Problem: Compute tree height Problem Introduction Trees are used to manipulate hierarchical data such as hierarchy of categories of a retailer or the directory structure on your computer. They are also used in data analysis and machine learning both for hierarchical clustering and building complex predictive models, including some of the best-performing in practice algorithms like Gradient Boosting over Decision Trees and Random Forests. In the later modules of this course, we will introduce balanced binary search trees (BST) — a special kind of trees that allows to very efficiently store, manipulate and retrieve data. Balanced BSTs are thus used in databases for efficient storage and actually in virtually any non-trivial programs, typically via built-in data structures of the programming language at hand. In this problem, your goal is to get used to trees. You will need to read a description of a tree from the input, implement the tree data structure, store the tree and compute its height.
Problem Description Task. You are given a description of a rooted tree. Your task is to compute and output its height. Recall that the height of a (rooted) tree is the maximum depth of a node, or the maximum distance from a leaf to the root. You are given an arbitrary tree, not necessarily a binary tree. Input Format. The first line contains the number of nodes n. The second line contains n integer numbers from −1 to n−1 — parents of nodes. If the i-th one of them (0 ≤ i ≤ n−1) is −1, node i is the root, otherwise it’s 0-based index of the parent of i-th node. It is guaranteed that there is exactly one root. It is guaranteed that the input represents a tree. Constraints. 1 ≤ n ≤ 105. Output Format. Output the height of the tree. Time Limits. C: 1 sec, C++: 1 sec, Java: 6 sec, Python: 3 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec. Memory Limit. 512MB. Sample 1. Input: 5 4 -1 4 1 1 Output: 3 Explanation: The input means that there are 5 nodes with numbers from 0 to 4, node 0 is a child of node 4, node 1 is the root, node 2 is a child of node 4, node 3 is a child of node 1 and node 4 is a child of node 1. To see this, let us write numbers of nodes from 0 to 4 in one line and the numbers given in the input in the second line underneath: 0 1 2 3 4 4 -1 4 1 1 Now we can see that the node number 1 is the root, because −1 corresponds to it in the second line. Also, we know that the nodes number 3 and number 4 are children of the root node 1. Also, we know that the nodes number 0 and number 2 are children of the node 4.
6
1root
3 4
0 2
The height of this tree is 3, because the number of vertices on the path from root 1 to leaf 2 is 3. Sample 2. Input: 5 -1 0 4 0 3 Output: 4
Explanation: The input means that there are 5 nodes with numbers from 0 to 4, node 0 is the root, node 1 is a child of node 0, node 2 is a child of node 4, node 3 is a child of node 0 and node 4 is a child of node 3. The height of this tree is 4, because the number of nodes on the path from root 0 to leaf 2 is 4.
0root
1 3
4
2
Starter Files The starter solutions in this problem read the description of a tree, store it in memory, compute the height in a naive way and write the output. You need to implement faster height computation. Starter solutions are available for C++, Java and Python3, and if you use other languages, you need to implement a solution from scratch.
What to Do To solve this problem, change the height function described in the lectures with an implementation which will work for an arbitrary tree. Note that the tree can be very deep in this problem, so you should be careful to avoid stack overflow problems if you’re using recursion, and definitely test your solution on a tree with the maximum possible height.
Suggestion: Take advantage of the fact that the labels for each tree node are integers in the range 0..n−1: you can store each node in an array whose index is the label of the node. By storing the nodes in an array, you have O(1) access to any node given its label. Create an array of n nodes:
7
allocate nodes[n] for i ← 0 to n−1: nodes[i] =new Node
Then, read each parent index: for child_index ← 0 to n−1: read parent_index if parent_index == −1: root ← child_index else: nodes[parent_index].addChild(nodes[child_index])
Once you’ve built the tree, you’ll then need to compute its height. If you don’t use recursion, you needn’t worry about stack overflow problems. Without recursion, you’ll need some auxiliary data structure to keep track of the current state (in the breadth-first seach code in lecture, for example, we used a queue).
Need Help? Ask a question or see the questions asked by other learners at this forum thread.
8
3 Advanced Problem: Network packet processing simulation Westronglyrecommendyoustartsolvingadvancedproblemsonlywhenyouaredonewiththebasicproblems (for some advanced problems, algorithms are not covered in the video lectures and require additional ideas to be solved; for some other advanced problems, algorithms are covered in the lectures, but implementing them is a more challenging task than for other problems).
Problem Introduction In this problem you will implement a program to simulate the processing of network packets.
Problem Description Task. You are given a series of incoming network packets, and your task is to simulate their processing. Packets arrive in some order. For each packet number i, you know the time when it arrived Ai and the time it takes the processor to process it Pi (both in milliseconds). There is only one processor, and it processes the incoming packets in the order of their arrival. If the processor started to process some packet, it doesn’t interrupt or stop until it finishes the processing of this packet, and the processing of packet i takes exactly Pi milliseconds.
The computer processing the packets has a network buffer of fixed size S. When packets arrive, they are stored in the buffer before being processed. However, if the buffer is full when a packet arrives (there are S packets which have arrived before this packet, and the computer hasn’t finished processing any of them), it is dropped and won’t be processed at all. If several packets arrive at the same time, they are first all stored in the buffer (some of them may be dropped because of that — those which are described later in the input). The computer processes the packets in the order of their arrival, and it starts processing the next available packet from the buffer as soon as it finishes processing the previous one. If at some point the computer is not busy, and there are no packets in the buffer, the computer just waits for the next packet to arrive. Note that a packet leaves the buffer and frees the space in the buffer as soon as the computer finishes processing it. Input Format. The first line of the input contains the size S of the buffer and the number n of incoming network packets. Each of the next n lines contains two numbers. i-th line contains the time of arrival Ai and the processing time Pi (both in milliseconds) of the i-th packet. It is guaranteed that the sequence of arrival times is non-decreasing (however, it can contain the exact same times of arrival in milliseconds — in this case the packet which is earlier in the input is considered to have arrived earlier). Constraints. All the numbers in the input are integers. 1 ≤ S ≤ 105; 1 ≤ n ≤ 105; 0 ≤ Ai ≤ 106; 0 ≤ Pi ≤ 103; Ai ≤ Ai+1 for 1 ≤ i ≤ n−1. Output Format. For each packet output either the moment of time (in milliseconds) when the processor began processing it or −1 if the packet was dropped (output the answers for the packets in the same order as the packets are given in the input). Time Limits. C: 2 sec, C++: 2 sec, Java: 6 sec, Python: 8 sec. C#: 3 sec, Haskell: 4 sec, JavaScript: 6 sec, Ruby: 6 sec, Scala: 6 sec. Memory Limit. 512MB. Sample 1. Input: 1 0 Output:
9
Explanation: If there are no packets, you shouldn’t output anything. Sample 2. Input: 1 1 0 0 Output: 0 Explanation: The only packet arrived at time 0, and computer started processing it immediately. Sample 3. Input: 1 2 0 1 0 1 Output: 0 -1 Explanation: The first packet arrived at time 0, the second packet also arrived at time 0, but was dropped, because the network buffer has size 1 and it was full with the first packet already. The first packet started processing at time 0, and the second packet was not processed at all. Sample 4. Input: 1 2 0 1 1 1 Output: 0 1 Explanation: The first packet arrived at time 0, the computer started processing it immediately and finished at time 1. The second packet arrived at time 1, and the computer started processing it immediately.
Starter Files The starter solutions for C++, Java and Python3 in this problem read the input, pass the requests for processing of packets one-by-one and output the results. They declare a class that implements network buffer simulator. The class is partially implemented, and your task is to implement the rest of it. If you use other languages, you need to implement the solution from scratch.
What to Do To solve this problem, you can use a list or a queue (in this case the queue should allow accessing its last element, and such queue is usually called a deque). You can use the corresponding built-in data structure in your language of choice.
10
One possible solution is to store in the list or queue finish_time the times when the computer will finish processing the packets which are currently stored in the network buffer, in increasing order. When a new packet arrives, you will first need to pop from the front of finish_time all the packets which are already processed by the time new packet arrives. Then you try to add the finish time for the new packet in finish_time. If the buffer is full (there are already S finish times in finish_time), the packet is dropped. Otherwise, its processing finish time is added to finish_time.
If finish_time is empty when a new packet arrives, computer will start processing the new packet immediately as soon as it arrives. Otherwise, computer will start processing the new packet as soon as it finishes to process the last of the packets currently in finish_time (here is when you need to access the last element of finish_time to determine when the computer will start to process the new packet). You will also need to compute the processing finish time by adding Pi to the processing start time and push it to the back of finish_time.
You need to remember to output the processing start time for each packet instead of the processing finish time which you store in finish_time.
Need Help? Ask a question or see the questions asked by other learners at this forum thread.
11
4 General Instructions and Recommendations on Solving Algorithmic Problems Your main goal in an algorithmic problem is to implement a program that solves a given computational problem in just few seconds even on massive datasets. Your program should read a dataset from the standard input and write an answer to the standard output. Below we provide general instructions and recommendations on solving such problems. Before reading them, go through readings and screencasts in the first module that show a step by step process of solving two algorithmic problems: link.
4.1 Reading the Problem Statement You start by reading the problem statement that contains the description of a particular computational task as well as time and memory limits your solution should fit in, and one or two sample tests. In some problems your goal is just to implement carefully an algorithm covered in the lectures, while in some other problems you first need to come up with an algorithm yourself.
4.2 Designing an Algorithm If your goal is to design an algorithm yourself, one of the things it is important to realize is the expected running time of your algorithm. Usually, you can guess it from the problem statement (specifically, from the subsection called constraints) as follows. Modern computers perform roughly 108–109 operations per second. So, if the maximum size of a dataset in the problem description is n = 105, then most probably an algorithm with quadratic running time is not going to fit into time limit (since for n = 105, n2 = 1010) while a solution with running time O(nlogn) will fit. However, an O(n2) solution will fit if n is up to 103 = 1000, and if n is at most 100, even O(n3) solutions will fit. In some cases, the problem is so hard that we do not know a polynomial solution. But for n up to 18, a solution with O(2nn2) running time will probably fit into the time limit. To design an algorithm with the expected running time, you will of course need to use the ideas covered in the lectures. Also, make sure to carefully go through sample tests in the problem description.
4.3 Implementing Your Algorithm When you have an algorithm in mind, you start implementing it. Currently, you can use the following programming languages to implement a solution to a problem: C, C++, C#, Haskell, Java, JavaScript, Python2, Python3, Ruby, Scala. For all problems, we will be providing starter solutions for C++, Java, and Python3. If you are going to use one of these programming languages, use these starter files. For other programming languages, you need to implement a solution from scratch.
4.4 Compiling Your Program For solving programming assignments, you can use any of the following programming languages: C, C++, C#, Haskell, Java, JavaScript, Python2, Python3, Ruby, and Scala. However, we will only be providing starter solution files for C++, Java, and Python3. The programming language of your submission is detected automatically, based on the extension of your submission. We have reference solutions in C++, Java and Python3 which solve the problem correctly under the given restrictions, and in most cases spend at most 1/3 of the time limit and at most 1/2 of the memory limit. You can also use other languages, and we’ve estimated the time limit multipliers for them, however, we have no guarantee that a correct solution for a particular problem running under the given time and memory constraints exists in any of those other languages. Your solution will be compiled as follows. We recommend that when testing your solution locally, you use the same compiler flags for compiling. This will increase the chances that your program behaves in the
12
same way on your machine and on the testing machine (note that a buggy program may behave differently when compiled by different compilers, or even by the same compiler with different flags). ∙ C (gcc 5.2.1). File extensions: .c. Flags: gcc -pipe -O2 -std=c11