Course Information
Course Description
This course teaches empirical complexity reasoning through Python. Given a performance problem, students learn to identify the bottleneck, choose the right data structure or algorithm, implement the solution, and benchmark to prove the choice was correct. Every week teaches a new data structure or algorithm but always in service of one core skill: choosing the right tool and proving it was the right choice through measurement.
The course is delivered entirely through Google Colab notebooks. Each week uses one notebook containing the lesson and practice activities. Students work at their own pace within the weekly deadline.
Learning Outcomes
Upon successful completion of this course, the student will be able to:
- Analyze algorithm complexity using Big-O notation and verify predictions with empirical benchmarks.
- Evaluate Python built-in data structures (list, dict, set) by measuring their real operation costs.
- Select appropriate linear data structures (stack, queue, deque) based on access pattern requirements.
- Apply recursion and memoization to transform exponential algorithms into efficient solutions.
- Choose between O(n), O(log n), and O(1) approaches (linear search, binary search, hashing) based on data characteristics.
- Implement and benchmark tree-based structures (heaps, BSTs) for ordered and prioritized data access.
- Model network problems using graphs and apply BFS, DFS, and Dijkstra's algorithm appropriately.
- Apply dynamic programming to eliminate redundant computation and benchmark the improvement.
Weekly Schedule
| Week | Topic | Key Content | Weekly notebook |
|---|---|---|---|
| Phase 1 · Learning to Measure & Predict (Weeks 1-2) | |||
| 01 | The Measuring Mindset: Big-O & Benchmarking |
Big-O concepts, benchmark logic, matplotlib review | Week 1 notebook |
| 02 | Know Your Tools: Python Built-in Costs |
list/dict/set operation costs, membership benchmarks | Week 2 notebook |
| Phase 2 · First Data Structure Choices (Weeks 3-4) | |||
| 03 | The Right Queue: Stack, Queue & Deque |
Stack/Queue/Deque ADT, list pop(0) vs deque popleft benchmark | Week 3 notebook |
| 04 | Divide & Remember: Recursion & Memoization |
Recursion, call stack, memoization, naive vs memoized benchmark | Week 4 notebook |
| Phase 3 · Choosing Between O(n), O(log n), O(1) (Weeks 5-7) | |||
| 05 | Finding Things: Linear vs Binary Search |
Linear vs binary search, sorted data trade-off | Week 5 notebook |
| 06 | Ordering Things: Sorting Algorithms |
Insertion/merge/quick sort concepts and benchmarks | Week 6 notebook |
| 07 | Instant Lookup: Hashing |
Hash table concepts, dict lookup benchmarks | Week 7 notebook |
| Phase 4 · Hierarchical Structures (Weeks 8-10) | |||
| 08 | Always the Best: Heap & Priority Queue |
heapq module, sorted() vs heapq for top-k benchmark | Week 8 notebook |
| 09 | Hierarchical Data: Trees & Traversal |
Tree concept, in/pre/post/level-order traversal | Week 9 notebook |
| 10 | Ordered Hierarchy: Binary Search Trees |
BST search/insert, balanced vs skewed performance | Week 10 notebook |
| Phase 5 · Network Structures (Weeks 11-12) | |||
| 11 | Connected Data: Graphs, BFS & DFS |
Graph representation (adj list), BFS/DFS, shortest path by edges | Week 11 notebook |
| 12 | Weighted Paths: Dijkstra's Algorithm |
Dijkstra basics, weighted graph routing | Week 12 notebook |
| Phase 6 · Algorithmic Optimization (Week 13) | |||
| 13 | Trading Memory for Speed: Dynamic Programming |
DP classic problems, memoization/DP benchmarks | Week 13 notebook |
| Phase 7 · Proving Mastery (Week 14) | |||
| 14 | Final Project: Fast Log Indexer |
dict/set indexing, fast queries, benchmark report + plot + conclusion | Week_14.ipynb |
Course Delivery & Learning Contract
What Students Can Expect Every Week
- Protected class time: the 3-hour session starts and finishes according to the official timetable, with a visible agenda and planned breaks.
- Clear explanation: each major idea follows explain → worked example → prediction → test → interpretation.
- Questions and voice: questions are welcome throughout; checkpoints reserve explicit time for think-pair-explain, misconceptions, and open questions.
- Professional purpose: the course is designed for Mechatronics Engineering students and repeatedly connects concepts to real-time algorithms, robotics, embedded constraints, planning, and telemetry.
- Exam alignment: notebooks label the reasoning moves rehearsed on assessments. Exams use the same verbs and standards with new values or contexts.
- Materials: weekly notes, runnable examples, core practice, feedback checkpoints, optional extensions, and references are provided from the start of the term.
Assessment & Grading
| Component | Weight | Description |
|---|---|---|
| Midterm Exam | 50% | Written/practical exam covering Weeks 1-7 concepts |
| Final Exam | 50% | Comprehensive exam covering all 14 weeks |
Assessment consists only of the midterm exam (50%) and final exam (50%). Weekly notebooks, exercises, projects, demonstrations and presentations are ungraded practice; no weekly submission is required.
Practice Feedback Checklist
- Completeness: Core functionality explored during practice
- Correctness: Code produces expected output for given inputs
- Code quality: Readable variable names, proper indentation, comments where appropriate
- Benchmarking rigor: Evidence of proper measurement methodology, correct interpretation of results, and justified data structure choices
Course Policies
Attendance
Regular attendance is expected. Students who miss more than 30% of classes may be denied the right to take the final exam, per university regulations. Weekly notebooks are private practice and are not used as an attendance record.
Academic Honesty
All assessed exams and live demonstrations must represent your own understanding. You may discuss general approaches with classmates, but you must be able to explain and modify the code you demonstrate. The following are considered violations:
- Copying code from another student or external source without attribution
- Sharing your exercise solutions with other students
- Presenting AI-generated work that you cannot explain, test, or modify
AI Tool Usage
AI assistants (ChatGPT, Copilot, etc.) may be used as learning aids to understand concepts. However, you must be able to explain and modify any code you demonstrate. Exercises are designed to build your skills progressively — bypassing them with AI defeats the purpose and will leave you unprepared for exams.
Communication
For course-related questions, email arif.solmaz@istun.edu.tr with your course code (DSA) in the subject line. Office hours: Wednesday, 09:00–11:00 AM.
References & Resources
- Primary: Course notebooks (provided weekly via Google Colab)
- Python Documentation: docs.python.org — Official Python 3 reference
- Grokking Algorithms — Aditya Bhargava
- Problem Solving with Algorithms and Data Structures using Python — Brad Miller & David Ranum (free online)
- Introduction to Algorithms (CLRS) — Cormen, Leiserson, Rivest, Stein (reference)