Data Structures And Algorithms

Pre-Course Survey
Discussion Forum: DS & Algorithms
Introduction
Module 1: Programming Challenges
4 Topics | 1 Quiz
01. Introduction to this course
02. Background Reference
03. Programming Challenge
04. Stress Testing
DSA: Final Quiz for Module 1: Programming Challenges
Assignments for Module 1: Programming Challenges
1 Quiz
2_maximum_pairwise_product
Module 2: Warm-up
11 Topics | 4 Quizzes
05. What Algorithms to Learn?
06. Coming Up
07. Fibonacci Numbers I
08. Fibonacci Numbers II
09. Greatest Common Divisors I
10. Greatest Common Divisors II
Quiz – S1M2 GCD
11. Runtimes
12. Asymptotic Notation
13. Big-O Notation
14. Using Big-O
Quiz – S1M2 Log for using Big O
Quiz – S1M2 Big O
Quiz – S1M2 Growth Rate
15. Course Overview
Assignments for Module 2: Warm-up
8 Quizzes
1_fibonacci_number
2_last_digit_of_fibonacci_number
3_greatest_common_divisor
4_least_common_multiple
5_fibonacci_number_again
6_last_digit_of_the_sum_of_fibonacci_numbers
7_last_digit_of_the_sum_of_fibonacci_numbers_again
8_last_digit_of_the_sum_of_squares_of_fibonacci_numbers
Algorithmic Tools
Module 1: Greedy Algorithms
 10 Topics | 6 Quizzes
16. Largest Number Problem
Quiz – S2M1 Largest Number Problem
17. Car Fueling Problem
18. Car Fueling Implementation & Analysis
Quiz – S2M1 Implementation and Analysis on Car Fueling Problem
19. Main Ingredients of Greedy Algorithms
Quiz – S2M1 Main Ingredients of Greedy Algorithms
20. Celebration Party Problem
21. Celebration Party Efficient Algorithm
22. Celebration Party Implementation & Analysis
Quiz – S2M1 Implementation and Analysis on Celebration Party Problem
23. Long Hike
24. Fractional Knapsack Implementation & Optimization
Quiz – S2M1 Implementation and Analysis on Fractional Knapsack Problem
25. Review of Greedy Algorithms
Quiz – S2M1 Last
Assignments for Module 1: Greedy Algorithms
 7 Quizzes
1_money_change
2_maximum_value_of_the_loot
3_car_fueling
4_maximum_advertisement_revenue
5_collecting_signatures
6_maximum_number_of_prizes
7_maximum_salary
Module 2: Divide-n-Conquer
 17 Topics | 5 Quizzes
26. Divide-n-Conquer Main Idea
27. Linear Search
28. Binary Search
29. Binary Search Runtime
Quiz – S2M2 Binary Search Runtime
30. Polynomial Multiplication
31. Naive Divide-n-Conquer
32. Faster Divide-n-Conquer
Quiz – S2M2 Faster Divide-n-Conquer for Polynomial Multiplication
33. Master Theorem
34. Proof of Master Theorem
Quiz – S2M2 Master Theorem
35. Selection Sort
36. Merge Sort
37. Lower Bound for Comparison Based Sorting
38. Non-comparison Based Sorting: Counting Sort
Quiz – S2M2 Non-comparison based Sorting: Counting Sort
39. Quick Sort
40. Random Pivot
41. Equal Elements
42. Final Remarks on Quick Sort
Quiz – S2M2 Last
Assignments for Module 2: Divide-n-Conquer
 5 Quizzes
1_binary_search
2_majority_element
3_improving_quicksort
4_number_of_inversions
5_closest_points
Module 3: Dynamic Programming
 14 Topics | 4 Quizzes
43. Coin Change Problem: Greedy Change
44. Recursive Coin Change
45. DP Coin Change
Quiz – S2M3 DP Coin Change
46. String Comparison: The Alignment Game
47. Computing Edit Distance
Quiz – S2M3 Computing Edit Distance
48. Reconstructing an Optimal Alignment
49. Knapsack: Problem Overview
Quiz – S2M3 Knapsack Problem Overview
50. Knapsack with Repetitions
51. Knapsack without Repetitions
52. Final Remarks on Knapsack Problem
53. Parentheses Problem
Quiz – S2M3 Parentheses Problem
54. Placing Parentheses: Subproblems
55. Placing Parentheses: Algorithm
56. Reconstructing a Solution
Assignments for Module 3: Dynamic Programming
 7 Quizzes
1_money_change_again
2_primitive_calculator
3_edit_distance
4_longest_common_subsequence_of_two_sequences
5_maximum_amount_of_gold
6_partitioning_souvenirs
7_maximum_value_of_an_arithmetic_expression
Data Structures
Module 1: Basic Data Structures
 9 Topics | 5 Quizzes
57. Arrays
Quiz – S3M1 Arrays
58. Singly-Linked Lists
Quiz – S3M1 Singly-linked List
59. Doubly-Linked Lists
60. Stacks
61. Queues
Quiz – S3M1 Queues
62. Trees
63. Tree Traversal
Quiz – S3M1 Tree Traversal
64. Dynamic Arrays
65. Amortized Analysis: Aggregate Method
Quiz – S3M1 Last
Assignments for Module 1: Basic Data Structures
 3 Quizzes
1_brackets_in_code
2_tree_height
5_max_sliding_window
Module 2: Priority Queues & Disjoint Sets
 14 Topics | 2 Quizzes
66. Priority Queues: Introduction
67. Priority Queues: Naive Implementation
68. Binary Heaps
69. Basic Operations
70. Complete Binary Trees
71. Pseudocode
72. Heap Sort
73. Building a Heap
74. Heap: Final Remarks
Quiz – S3M2 Final Remarks of Heap
75. Disjoint Sets: Overview
76. Disjoint Sets: Naive Implementation
77. Disjoint Sets: Tree Representation
78. Union by Rank
79. Path Compression
Quiz – S3M2 Last
Assignments for Module 2: Priority Queues & Disjoint Sets
Module 3: Hash Tables
 17 Topics | 2 Quizzes
80. Applications of Hashing
81. Analyzing Service Access Logs
82. Direct Addressing
83. List-based Mapping
84. Hash Functions
85. Chaining Scheme
86. Chaining Implementation & Analysis
87. Hash Tables
88. Phone Book Problem
89. Universal Family
90. Hashing Integers
91. Hashing Strings
92. Hashing Strings – Cardinality Fix
Quiz – S3M3 Hashing Strings-Cardinality Fix
93. Search Pattern in Text
94. Rabin-Karp’s Algorithm
95. Optimization: Precomputation
96. Optimization: Implementation & Analysis
Quiz – S3M3 Last
Assignments for Module 3: Hash Tables
 1 Quiz
3_hash_substring
Module 4: Binary Search Trees
 10 Topics | 2 Quizzes
97. Introduction
98. Search Trees
99. Basic Operations
100. Balance
101. AVL Trees: Introduction
102. AVL Trees: Implementation
103. Split and Merge
Quiz – S3M4 Split and Merge
104. Applications
105. Splay Trees: Introduction
106. Splay Trees: Implementation
Quiz – S3M4 Last
Assignments for Module 4: Binary Search Trees
 2 Quizzes
2_is_bst
3_is_bst_advanced
Graph Algorithms
Module 1: Decomposition of Graphs
 9 Topics | 2 Quizzes
107. Graph Basics
108. Representing Graphs
109. Exploring Graphs
110. Connectivity
111. Previsit and Postvisit Orders
Quiz – S4M1 Previsit and Postvisit Orders
112. Directed Acyclic Graphs
113. Topological Sort
114. Strongly Connected Components
115. Computing SCCs
Quiz – S4M1 Last
Assignments for Module 1: Decomposition of Graphs
 5 Quizzes
1_reachability
2_connected_components
3_acyclicity
4_toposort
5_strongly_connected
Module 2: Paths in Graphs
 20 Topics | 3 Quizzes
116. Most Direct Route
117. Breadth First Search I
118. Breadth First Search II
119. BFS: Implementation & Analysis
120. Proof of Correctness I
121. Proof of Correctness II
122. Shortest-Path Tree
123. Reconstructing the Shortest Path
Quiz – S4M2 Reconstructing the Shortest Path
124. Fastest Route
125. Naive Algorithm
126. Dijkstra’s Algorithm: Intuition & Example
127. Dijkstra’s Algorithm: Implementation
128. Dijkstra’s Algorithm: Proof of Correctness
129. Dijkstra’s Algorithm: Running Time
Quiz – S4M2 Running time of Dijkstra’s Algorithm
130. Currency Exchange
131. Reduction to Shortest Paths
132. Bellman-Ford Algorithm
133. Proof of Correctness
134. Negative Cycles
135. Infinite Arbitrage
Quiz – S4M2 Last
Assignments for Module 2: Paths in Graphs
 4 Quizzes
1_bfs
2_bipartite
3_dijkstra
4_negative_cycle
Module 3: Spanning Trees
 5 Topics
136. Building a Network
137. Greedy Algorithms
138. Cut Property
139. Kruskal’s Algorithm
140. Prim’s Algorithm
Assignments for Module 3: Spanning Trees
 2 Quizzes
1_connecting_points
2_clustering
User Feedback on This Course

Quiz – S1M2 Log for using Big O

Data Structures And Algorithms Module 2: Warm-up 14. Using Big-O Quiz – S1M2 Log for using Big O

The goal of this assignment is to practice with logarithms that appear frequently in the analysis of algorithms.

Recall that  is the power to which you need to raise  in order to obtain .

The main rules for working with logarithms are the following:

Quiz – S1M2 Log for using Big O

Answer the following question by selecting True or False according to the correctness of the statement.

×

Cart