Course Design (draft)
Algorithm Problem Solving
Mission: Learn to Solve Problems
Purpose - Individual: Improve ability to
solve problems, develop efficient SW. Improve hiring opportunities, get more
visibility with better ranks in online portals e.g. hackerrank, get better rank
in competitions e.g., IOI, ICPC, Google Code Jam etc
Purpose - Institute: Attract more
companies, more companies with better work profile, get more visibility with
better results in IOI/ICPC
Course Design
1.
Duration:
~50-Hours / 4-5 months
2.
Pre-Requisites:
Data Structures / Algorithms
3.
Main Contents
3.1.
Problem Solving
Methods (Solving, Solving Efficiently, Solving Quickly)
3.2.
Advanced Algo/DS
4.
Evaluation:
Scoring for regular tests, final test.
Problem Solving Process
1.
Understand the
Problem
1.1.
understand story
line
1.2.
understand
inputs, data, conditions, constraints
1.3.
understand
unknowns, expectation
1.4.
How to handle
missing info, contradictory info, and ambiguous info?
2.
What is the main
focus?
2.1.
Comprehension
2.2.
Functionality
2.3.
Corners, Boundaries
2.4.
Large Data
handling
2.5.
Online, Dynamic
data handling
2.6.
Speed? Memory?
Cost?
2.7.
Combinations of
above
3.
Identify the
Problem Domain
3.1.
Puzzles, Find
Paths, cost minimization, Data Analysis, machine learning, electrical networks,
mechanical engg, civil engg... (make sure there is no dependency on knowledge
of these domains.)
3.2.
Fully offline solutions
3.3.
Partial offline
solution + partial programmatic solutions
3.4.
Fully
programmatic solutions
4.
Identify the
Problem Type
4.1.
Searching,
Sorting problems
4.2.
Tree/Graph
problems
4.3.
Grid problems
4.4.
Combinatorics
problems
4.5.
Geometric
problems
4.6.
Numerical
problems
4.7.
Fixed data handling
vs. Dynamic data handling
5.
Identify suitable
problem Solving Paradigms/Method
5.1.
Brute force,
Exhaustive search
5.2.
Decrease and
Conquer, Divide and Conquer, Transform and Conquer
5.3.
Space and Time
trade-off
5.4.
Greedy technique
5.5.
Dynamic
Programming
5.6.
Approximation,
Iterative improvement
5.7.
Randomization,
5.8.
Pre-Processing
6.
Break down into
sub problems.
6.1.
Identify known similar
problems? Identify solutions?
6.2.
Mapping problems
to solutions (building blocks)
6.2.1. Solutions to sub problems. Multiple approaches.
Multiple solutions.
6.2.2. Find multiple solutions to sub problems (as per
expectation... i.e., main focus is functionality or speed?)
6.3.
Building up the
overall solution… Find a coherent set of solutions to all sub-problems.
6.4.
Building Blocks /
Patterns: DS/Algo, Learn from Other Disciplines (Transfer learning)?
6.4.1. Learn from SW Design Patterns (functional focus)
6.4.2. Learn from SW Architecture Patterns (quality focus)
6.4.3. Learn from invention patterns e.g. TRIZ, ARIZ.
6.4.4. Structural, Behavioral patterns
7.
Problem
Complexity Gradation
7.1.
Solve completely
offline (programming not required)
7.2.
Solve completely
programmatic
7.3.
Partial offline
and programmatic
8.
Complexity Levels
8.1.
Teach how same
problem with different constraints demand different solutions
8.2.
E.g. (1) Linear
Search -> Binary Search -> Hash Table
8.3.
E.g. (2) Bubble
Sort -> Quick Sort -> Counting Sort
8.4.
Heavy on data
reading or data updating?
8.5.
How to handle
dynamic data? How to handle large data?
8.6.
How to handle
sparse data (sparse matrix)?
8.7.
Is the complexity
based on number of data-points or range of data values?
Solving Efficiently
1.
First solve, improve
later.
2.
Improving
Solution
2.1.
Improve
Efficiency
2.2.
Pre-Processing
2.3.
Common work for
all test-cases
3.
Solving Quickly
1.
Time limit of 1
or 2-hours/problem, or multiple problems within 3-4 hours.
2.
Perfection in building
blocks: practice a lot… Solve many small problems… again and again from
scratch.
3.
Quick coding of
template of a solution pattern/style… e.g., most DFS solutions has a specific
code outline.
4.
Testing practices,
Debugging practices
5.
Quick resolution
of bugs – tests to locate a known bug.
6.
Tests to uncover
unknown bugs.
Testing
1.
Test case Design
1.1.
TC for basic
functionality
1.2.
TC complexity
functionality
1.3.
TC for
boundaries, corners
1.4.
TC for large data
handling
1.5.
TC for efficiency
testing
2.
Testing /
Debugging
2.1.
Testing with one
TC at a time
2.2.
Testing with
multiple TC
2.3.
Accumulate TC
2.4.
Manual TC writing
2.5.
Programmatic TC
generation
2.6.
Testing Methods
2.7.
Typical mistakes,
types of errors
2.8.
Understand what
failed from achieved score
Learning
1.
Problem Breakdown
2.
Problem Mapping
to Solutions
3.
Building Blocks
4.
Learn from
Mistakes, Errors
Miscellaneous
1.
Misc :
Visualization
1.1.
Visual tracing or
program's execution: https://visualgo.net/en
1.2.
Visual Graph
Traversal - http://chengyichao.info/visual-graph-traversal/
1.3.
Path finding in
grid – visualization
1.4.
Result
Visualization
2.
Misc
2.1.
Dynamic
Programming (sub-problems, overlapping, optimality?)
2.2.
Show that DFS/BFS
are traversal over the options represented as a tree...
2.3.
When to use DFS
or BFS?
2.4.
DFS - pruning,
backtracking, memorization...
3.
Best Practices
3.1.
Grid problems (1)
separate function for checking coordinate validity (boundary checking) (2)
separate function for checking validity of current cell for current
situation...
3.2.
Backtracking -
use an array for levels of data
4.
Misc : Capability
4.1.
Data Structures,
Algorithms, Building Blocks
4.2.
Logical Thinking
4.3.
Mathematics
4.4.
Programming
(C/C++/Java....)
4.5.
Code
Designing/Structuring
4.6.
Speed of Coding
5.
Evaluation
5.1.
Scoring Methods
5.2.
Ranking Methods
5.3.
Absolute,
Relative, Clusters...
5.4.
Better than Goal,
Near to Best...
5.5.
Final Evaluation
:
5.5.1. Written quiz?
5.5.2. Based on 1 final test?
5.5.3. Pass at least 2 of 3 tests in the last month?
5.5.4. Consider accumulated score/rank, regular
learning/practice, diversity of topics, complexity levels.
6.
For Problem
Setter
6.1.
Problem setting
philosopy / guide
6.2.
Test-Case
classification, post-test analysis, share results
7.
For Teacher
7.1.
Teaching methods
8.
Environments:
8.1.
How online judge
tools work
8.2.
Full code writing
vs. API code writing
8.3.
Memory
allocation: max memory vs. on-demand memory
9.
Online Courses
9.1.
abcd
10.
Books
10.1.The Algorithm Design Manual, Steven S. Skiena
10.2.Introduction to the Design and Analysis of Algorithms - Anany Levitin
10.4.Algorithm Design - Jon
Kleinberg, Eva Tardos
