Data Structures Assignment 2
Instructions:
Provide well-commented code for programming questions.
Justify your answers with time and space complexity analysis where applicable.
Submit your solutions as a document or notebook (C++ supported).
Assignment Questions
1. Doubly Linked List Operations (5 Marks)
Reference: Wengrow Ch14
Scenario:
You are working on a music streaming app that maintains a playlist using a doubly linked list.
Each song in the playlist has a next and previous pointer to support both forward and
backward navigation.
Tasks:
a) Implement a Doubly Linked List (DLL) with the following functions:
addSong(string songName): Adds a song at the end of the playlist.
deleteSong(string songName): Deletes a specific song from the playlist.
displayForward(): Displays the playlist in the forward direction.
displayBackward(): Displays the playlist in the reverse direction.
b) Optimize the deletion operation to run in O(1) time if the node reference is given. Explain
how this optimization is achieved.
2. Circular Linked List (3 Marks)
Reference: Wengrow Ch14
Scenario:
A circular linked list is useful in multiplayer gaming, where turns are assigned cyclically.
Your task is to simulate a game turn rotation using a circular linked list.
Tasks:
a) Implement a Circular Linked List where players are inserted dynamically.
b) Write a function nextTurn() that moves to the next player and prints their name.
c) Optimize your implementation to ensure O(1) insertion at both the head and tail.
3. Stack: Static & Dynamic Implementation (3 Marks)
Reference: Wengrow Ch9
Scenario:
A browser stores visited pages using a stack to enable the "Back" and "Forward" navigation
feature.
Tasks:
a) Implement a static stack (fixed-size array) and a dynamic stack (linked list-based).
b) Implement the following stack operations:
push(string url): Adds a URL to the stack.
pop(): Removes the most recent URL.
peek(): Shows the most recent URL without removing it.
c) Compare static vs. dynamic implementation in terms of memory usage and
efficiency.
4. Infix to Postfix Conversion using Stack (4 Marks)
Reference: Weiss Ch3
Scenario:
You are building a calculator app that requires evaluating expressions efficiently. Since postfix
expressions can be evaluated faster than infix expressions, your task is to implement the
conversion.
Tasks:
a) Convert the following infix expression into postfix notation using a stack:
b) Implement using C++ to automate this conversion.
c) Justify your approach with an algorithmic breakdown.
5. Queue: Static & Dynamic Implementation (3 Marks)
Reference: Wengrow Ch9, Weiss Ch3
Scenario:
A customer service center uses a queue to manage incoming calls. Your task is to implement
both static and dynamic queues for call handling.
Tasks:
a) Implement a static queue (array-based) and a dynamic queue (linked list-based).
b) Implement the following operations:
enqueue(int callID): Adds a call to the queue.
dequeue(): Serves the next call in the queue.
peek(): Shows the next call without dequeuing.
c) Compare static vs. dynamic queues in terms of efficiency and memory allocation.
6. Circular Queue & Priority Queue (4 Marks)
Reference: Wengrow Ch9, Weiss Ch3
Scenario:
A CPU scheduler handles multiple processes where some are high-priority tasks and must be
executed first. You need to implement a Priority Queue using a Circular Queue.
Tasks:
a) Implement a Circular Queue with wrap-around indexing.
b) Implement a Priority Queue where:
Higher priority tasks are executed first.
If two tasks have the same priority, they are executed in FIFO order.
c) Analyze the worst-case complexity for both implementations.
7. Double Ended Queue (Deque) (3 Marks)
Reference: Wengrow Ch9
Scenario:
A text editor maintains an undo/redo feature using a double-ended queue (Deque).
Tasks:
a) Implement a Deque that supports the following operations:
insertFront(string operation): Adds an operation at the front.
insertRear(string operation): Adds an operation at the rear.
deleteFront(): Removes an operation from the front.
deleteRear(): Removes an operation from the rear.
b) Explain how this implementation can be used for an undo/redo feature.
c) Discuss the time complexity of all operations.
Submission Guidelines
Submit your well-commented source code and a report on CUONLINE
Include algorithmic explanations and complexity analysis for each question.
Code must be error-free and optimized for efficiency.
Due time does not mean time of submission. You can submit your work before the
deadline as well