|
1 | | -A---------------------------------------------- |
2 | | - |
3 | | - |
4 | | -OBJECTIVE - Become A Competitive Programmer |
5 | | - |
6 | | - |
7 | | ----------------------------------------------- |
8 | 1 |
|
| 2 | +**“For me, great algorithms are the poetry of |
| 3 | +computation. Just like verse, they can be terse, |
| 4 | +allusive, dense, and even mysterious. |
| 5 | +But once unlocked, they cast a brilliant new |
| 6 | +light on some aspect of computing.” |
| 7 | +— Francis Sullivan** |
9 | 8 |
|
10 | | -“ For me, great algorithms are the poetry of |
11 | | - computation. Just like verse, they can be terse, |
12 | | - allusive, dense, and even mysterious. |
13 | 9 |
|
14 | | - But once unlocked, they cast a brilliant new |
15 | | - light on some aspect of computing. ” |
| 10 | +**“An algorithm must be seen to be believed.” |
| 11 | +— Donald Knuth** |
16 | 12 |
|
17 | | -— Francis Sullivan |
18 | 13 |
|
| 14 | +**“I will, in fact, claim that the difference |
| 15 | +between a bad programmer and a good one is |
| 16 | +whether he considers his code or his data |
| 17 | +structures more important. |
| 18 | +Bad programmers worry about the code. |
| 19 | +Good programmers worry about data structures and |
| 20 | +their relationships.” — Linus Torvalds** |
19 | 21 |
|
20 | | ----------------------------------------------- |
21 | 22 |
|
| 23 | +**“Algorithms + Data Structures = Programs.” |
| 24 | +— Niklaus Wirth`** |
22 | 25 |
|
23 | | -“ An algorithm must be seen to be believed. ” |
24 | 26 |
|
25 | | -— Donald Knuth |
| 27 | +#Code Challenge |
26 | 28 |
|
| 29 | +Code challenge solutions from different sources |
| 30 | +in Java by@codeanit. |
27 | 31 |
|
28 | | ----------------------------------------------- |
| 32 | +I do this because I want to improve my problem |
| 33 | +solving and technical skills and keep my competitive edge. |
29 | 34 |
|
30 | 35 |
|
31 | | -“ I will, in fact, claim that the difference |
32 | | -between a bad programmer and a good one is |
33 | | -whether he considers his code or his data |
34 | | -structures more important. |
| 36 | +###How to become good at code challenges? |
35 | 37 |
|
36 | | -Bad programmers worry about the code. |
| 38 | +**#Observe #Introspect #Retrospect #Refactor** |
37 | 39 |
|
38 | | -Good programmers worry about data structures |
39 | | -and their relationships. ” |
| 40 | +#####Understand The Basics |
| 41 | +Don't skip basics, mathematics, data structures |
| 42 | +and algorithms. Mathematics helps build a solution. |
| 43 | +The data structures are the tools and the algorithms |
| 44 | +are the techniques that are the arsenal that every |
| 45 | +good programmer must have, more the better. Else, |
| 46 | +you will only see`a hammer and a nail`. |
40 | 47 |
|
41 | | -— Linus Torvalds |
| 48 | +#####Know The Process |
| 49 | +To solve the challenge, start with trivial, slow |
| 50 | +ideas to form a heuristic technique, and then |
| 51 | +improve towards creative, fast algorithms which |
| 52 | +could be solved with specific techniques. So just |
| 53 | +solve as you can first even the exponential solution |
| 54 | +if it works it's fine, be greatful. |
42 | 55 |
|
| 56 | +Start by solving easy problems, then medium, and |
| 57 | +finally the difficult ones. Try different types |
| 58 | +of problems from different sources. |
43 | 59 |
|
44 | | ----------------------------------------------- |
| 60 | +Learn from other's solution and compare with your |
| 61 | +own. Try to understand what other did differently |
| 62 | +and analyse what can be improved, both in your |
| 63 | +solution as well as others. This will help add more |
| 64 | +dimensions to problem analysis and solutions ideas. |
45 | 65 |
|
| 66 | +Improve your understanding by trying to answer |
| 67 | +Why was it done this way?. |
46 | 68 |
|
47 | | -“ Algorithms + Data Structures = Programs. ” |
| 69 | +#####Estimate The Complexity |
| 70 | +The time limit set for online tests is usually |
| 71 | +from 1 to 10 seconds. We can therefore estimate |
| 72 | +the expected complexity. During contests, we are |
| 73 | +often given a limit on the size of data, and |
| 74 | +therefore we can guess the time complexity within |
| 75 | +which the task should be solved. This is usually |
| 76 | +a great convenience because we can look for a |
| 77 | +solution that works in a specific complexity instead |
| 78 | +of worrying about a faster solution. |
| 79 | +For example, if: |
| 80 | +• n <= 1 000 000, the expected time complexity is O(n) or O(nlogn), |
| 81 | +• n <= 10 000, the expected time complexity is O(n^2), |
| 82 | +• n <= 500, the expected time complexity is O(n^3). |
48 | 83 |
|
49 | | -— Niklaus Wirth |
| 84 | +Of course, these limits are not precise. They are |
| 85 | +just approximations, and will vary depending on the |
| 86 | +specific task. |
50 | 87 |
|
51 | 88 |
|
52 | | ----------------------------------------------- |
| 89 | +#Folders |
| 90 | +`resource` folder contains learning materials. |
53 | 91 |
|
54 | 92 |
|
55 | | -Hi. I am Anit and I am a ever learning |
56 | | -student of mathematics and computer science. |
| 93 | +#Objective |
| 94 | +Objective of the repository to cover this list below: |
57 | 95 |
|
58 | | -I have worked for many years as a software |
59 | | -development engineer and I believe that I |
60 | | -have to keep myself skilled so from time to |
61 | | -time I have to go through the datastructures again |
62 | | -and after. Keep updated with the newer |
63 | | -technologies is a must but not at the cost |
64 | | -of forgetting or weakening the datastructures that |
65 | | -are fundamentals of any technology. |
| 96 | +- Mathematics: Prime Number, Big Integer, Permutation, |
| 97 | + Number Theory, Factorial, Fibonacci, Sequences, |
| 98 | + Modulus |
66 | 99 |
|
67 | | -Hence, the objective of this repository is |
68 | | -personal growth and development of programming |
69 | | -skills. |
| 100 | +- Dynamic Programming: Longest Common Subsequence, |
| 101 | + Longest Increasing Subsequence, Edit Distance, |
| 102 | + 0/1 Knapsack, Coin Change, Matrix Chain Multiplication, |
| 103 | + Max Interval Sum |
70 | 104 |
|
71 | | -The repository contains the code challenges |
72 | | -and their solutions from different sources. |
73 | | -Also includes implementation of basic data |
74 | | -structures and algorithms. |
| 105 | +- Graph Traversal: Flood Fill,Floyd Warshal, MST, |
| 106 | + Max Bipartite Matching, Network Flow, |
| 107 | + Articulation Point |
75 | 108 |
|
76 | | -The code base is Java. |
| 109 | +- Sorting: Bubble Sort, Quick Sort, Merge Sort, |
| 110 | + Selection Sort, Radix Sort, Bucket Sort |
77 | 111 |
|
78 | | -Books and other resources can be found at the |
79 | | -"notes" folder. |
| 112 | +- Searching: Complete Search, Brute Force, Binary Search |
80 | 113 |
|
| 114 | +- String Processing: String Matching, Pattern Matching |
81 | 115 |
|
82 | | ----------------------------------------------- |
83 | | - |
84 | | - |
85 | | -References from Princeton University to |
86 | | -re-enforce the basic and advance programming |
87 | | -skills: |
88 | | - |
89 | | -https://introcs.cs.princeton.edu/java/home/ |
90 | | -https://www.coursera.org/learn/cs-programming-java |
91 | | - |
92 | | -https://algs4.cs.princeton.edu/ |
93 | | -https://www.coursera.org/learn/algorithms-part1/ |
94 | | -https://www.coursera.org/learn/algorithms-part2/ |
95 | | - |
96 | | -https://aofa.cs.princeton.edu/home/ |
97 | | -https://www.coursera.org/learn/analysis-of-algorithms/ |
98 | | - |
99 | | -https://ac.cs.princeton.edu/home/ |
100 | | -https://www.coursera.org/learn/analytic-combinatorics |
101 | | - |
102 | | - |
103 | | -I am forever greatful to Princeton University |
104 | | -and it's outstanding faculty for making these |
105 | | -online resources free, and especially Robert |
106 | | -Sedgewick & Kevin Waynefor excellent contents. |
107 | | - |
108 | | - |
109 | | ----------------------------------------------- |
110 | | - |
111 | | - |
112 | | -Recently came to know about a playlist on |
113 | | -Algorithms by Abdul Bari on YouTube. I am |
114 | | -very thankful to his effort on making very |
115 | | -hard things easy to understand. |
116 | | - |
117 | | -youtube.com/watch?v=e2cF8a5aAhE&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O |
118 | | - |
119 | | - |
120 | | ----------------------------------------------- |
121 | | - |
122 | | - |
123 | | -Resources for Software Engineers |
124 | | - |
125 | | -Clean Code by Robert C. Martin |
126 | | -Design Patterns by The Gang of Four |
127 | | -Design Principles like SOLID, DRY |
128 | | -Test Driven Development by Kent Beck |
129 | | -Refactoring by Martin Fowler |
130 | | -Introduction to Algorithms by CLRS |
131 | | -Algorithm Design by Kleinberg & Tardos |
132 | | -http://algorist.com/algorist.html |
133 | | - |
134 | | ----------------------------------------------- |
135 | | - |
136 | | - |
137 | | -Contents of the repository to cover this list |
138 | | - |
139 | | -- Mathematics : Prime Number, Big Integer, Permutation, |
140 | | - Number Theory, Factorial, Fibonacci, Sequences, |
141 | | - Modulus |
142 | | - |
143 | | -- Dynamic Programming : Longest Common Subsequence, |
144 | | - Longest Increasing Subsequence, Edit Distance, |
145 | | - 0/1 Knapsack, Coin Change, Matrix Chain Multiplication, |
146 | | - Max Interval Sum |
147 | | - |
148 | | -- Graph Traversal : Flood Fill,Floyd Warshal, MST, |
149 | | - Max Bipartite Matching, Network Flow, |
150 | | - Articulation Point |
151 | | - |
152 | | -- Sorting : Bubble Sort, Quick Sort, Merge Sort, |
153 | | - Selection Sort, Radix Sort, Bucket Sort |
154 | | - |
155 | | -- Searching : Complete Search, Brute Force, Binary Search |
156 | | - |
157 | | -- String Processing : String Matching, Pattern Matching |
158 | | - |
159 | | -- AdHoc Problems: Trivial Problems |
160 | | - |
161 | | - |
162 | | ----------------------------------------------- |
163 | | - |
164 | | - |
165 | | -If in anyway I can be of any help with my skills of |
166 | | -programming, I will undoubtably be willing to help. |
167 | | -Please do not hesitate to reach out to me! |
168 | | - |
169 | | -codeanit@gmail.com |
170 | | - |
171 | | - |
172 | | ----------------------------------------------- |
173 | | - |
174 | | - |
175 | | -TODO: Update this file. |
176 | | -1. Add unit tests. |
177 | | -2. Implement CI to run the unit tests. |
178 | | - |
| 116 | +- AdHoc Problems: Trivial Problems |