Software Development - Clean Code, Data Structures, and Algorithms

Readings and Resources:

Required Reading:

Lecture:

• Book: Algorithms and Data Structures with Python
• Website (currently porting to Rust): https://dominikboehler.de/CS2Plus

Exercise:

• Guide to Competitive Programming

Tutorial:

• Programming Rust

Additional Resources

• https://rust-exercises.com/
• Rustlings
• Rust Book, Brown University with great quizzes:
• Rust by Example: https://doc.rust-lang.org/rust-by-example/index.html
• Algorithms and Data Structures in Rust (Second half)

Competitive Programming Deliverables

In each exercise we will attempt a challenging algorithmic problem from the CSES Problemset: https://cses.fi/problemset/

Use this template for Rust Code: https://github.com/dominikb1888/cses_template

Class Design - Flipped Classroom

The course is taught in a Flipped Classroom style. You are required to prepare coding exercises and will be asked to present them in front of class on a random selection basis.

• 30 min

  Review and joint development of selected Homework Exercises

• 60 min

  Theoretical input on computational thinking with Algorithms and Data Structures.

• 90 min

  Applying theoretical input in a hands-on class project: Building a text editor (https://github.com/dominikb1888/rim).

Exam (graded)

The Exam will be written and online. It will be a code exercise just like the ones you practice with tests provided.

Agenda

1. Algorithms Analysis, Design and Evaluation (Chapter 2)
2. Recursion
3. Sequences
4. Sets and Maps
5. Trees
6. Graphs
7. Membership Structures
8. Heaps
9. Balanced Binary Search Trees
10. B-Trees
11. Heuristic Search

Deliverables

Sessions

1. Algorithms: Analysis, Design, and Evaluation

Lecture:

• Introduction to Data Structures: Simple Linked List
• Introduction to Estimating Algorithm Runtime

In-class Exercise:

• Weird Algorithm

Required Reading:

• https://en.algorithmica.org/hpc/complexity/

Optional Reading

• https://nnethercote.github.io/perf-book/introduction.html
• https://towardsdatascience.com/benchmarking-rust-compiler-settings-with-criterion-62db50cd62fb
• https://patrickfreed.github.io/rust/2021/10/15/making-slow-rust-code-fast.html
• Last resort - Assembly Output: https://rust.godbolt.org/, https://darkcoding.net/software/underrust-rust-assembly-output/

2. Recursion

• Recap of Tower of Hanoi Excercise
• Understanding Recursion and its memory footprint
• The Stack, the Heap, Pointers and Recursion:
  • https://web.mit.edu/rust-lang_v1.25/arch/amd64_ubuntu1404/share/doc/rust/html/book/first-edition/the-stack-and-the-heap.html
  • https://www.varonis.com/blog/stack-memory-3
• Evaluating Algorithms (Recap of Session 1)

Exercise:

• Extending rim with a Linked List (Undo function)

3. Sequences

Interactive:

• Building a Linked List from Scratch (https://rust-unofficial.github.io/too-many-lists/)
• Rust Memory Allocation and Pointers

Data Structures:

• Linked Lists: Improving on our Exercise
• Doubly Linked Lists
• Skip Lists
• Dynamic Arrays (Vec):

Algorithms for Sorting and Ordering:

• Bubble Sort
• Merge Sort (Divide and Conquer)
• Quicksort

4. Maps and Sets

Algorithms:

• Hashing

Data Structures:

• Maps
• Sets

Reading:

• https://medium.com/better-programming/implementing-a-hashmap-in-rust-35d055b5ac2b
• https://edgl.dev/blog/rust-hashmap/
• https://nnethercote.github.io/perf-book/hashing.html#:~:text=The%20default%20hashing%20algorithm%20is,short%20keys%20such%20as%20integers
• https://en.wikipedia.org/wiki/Collision_attack
• https://link.springer.com/chapter/10.1007/978-3-642-34931-7_28
• https://www.reddit.com/r/rust/comments/52grcl/comment/d7kcei2/
• https://betterprogramming.pub/implementing-a-hashmap-in-rust-35d055b5ac2b
• https://louisabraham.github.io/articles/exact-cover
• https://www.geeksforgeeks.org/solving-sudoku-using-bitwise-algorithm/
• https://medium.com/@dt_emmy/sudoku-solver-using-rust-8a4e83d921fd

5. Trees

Data Structure:

• Heap
• Binary Search Tree
• Red-Black Tree
• Trie
• B-Tree

Algorithms

• Heap Sort

6. Graphs

• Graph Representation: Adjacency Matrix

7. Membership Structures

8. Heaps

9. Balanced Binary Search Trees

10. B-Trees

11. Heuristic Search

12. Practice and Mock Exam

13. Practice and Mock Exam

Further Reading

• The Rules of Programming