Commit 047f7e1
Changed files (1)
assignments
01
assignments/01/README.md
@@ -4,11 +4,11 @@ Answer question 1, question 2, and any other 2 questions from questions 3 to 6
You must score at least 50 to pass the assignment.
1. You have learned some fundamental data structure concepts such as array, queue and priority queue, stack, list and linked list, sequence, and unordered set, and you understand the concept of interface or abstract data type that defines the set of operations supported by a data structure and the semantics, or meaning, of those operations. You can use the interface of one particular data structure to define or implement the operations of a different data structure.
- a. Describe the meaning of the essential methods `add(x)`, `deleteMin()`, and `size()` that are supported by the priority queue interface. Implement those methods using a singly-linked list. Analyze the running time of the `add(x)` and `deletMin()` operations based on this implementation.
- b. Implement the stack methods `push(x)` and `pop()` using two queues. Analyze the running time of the `push(x)` and `pop()` operations based on this implementation.
+ * a. Describe the meaning of the essential methods `add(x)`, `deleteMin()`, and `size()` that are supported by the priority queue interface. Implement those methods using a singly-linked list. Analyze the running time of the `add(x)` and `deletMin()` operations based on this implementation.
+ * b. Implement the stack methods `push(x)` and `pop()` using two queues. Analyze the running time of the `push(x)` and `pop()` operations based on this implementation.
2. Swap two adjacent elements in a list by adjusting only the links (and not the data) using:
- a. singly-linked list.
- b. doubly-linked list.
+ * a. singly-linked list.
+ * b. doubly-linked list.
3. Using a `USet`, implement a `Bag`. A `Bag` is like a `USet` - it supports the `add(x)`, `remove(x)`, and `find(x)` methods - but it allows duplicate elements to be stored.
The `find(x)` operation in a Bag returns some element (if any) that is equal to x.
In addition, a `Bag` supports the `findAll(x)` operation that returns a list of all elements in the Bag that are equal to x.