A Practical Application Of Data Structures & Algorithms

Do you know what algorithm the native array find(...) or indexOf(...) function in your favorite programming language uses?

Have you considered what scenarios these in-built functions might not be the best pick for the job at hand, and what alternatives you'd need to explore?

Transcript

1. A Practical Application Of Data Structures & Algorithms 1 Charles Odili March,2024
2. Who Am I & Why Should You Care
3. @chaluwa linkedin.com/in/charlesodili From: Warri (Delta State, Nigeria) Background: Computer Engineering Now: Senior Software Engineer Exes: ex C.T.O, ex Andela, ex Google Fun Facts: • A bass player & was in a music group • Dated no one from 2005 till 2011 • Coding professionally since 2007 • Published a Java Book with Packt in 2012 • Once coded for 4 days without any sleep. Pls dont try it! • Really don’t know how to smile
4. The Battle-Ready Engineer - a.k.a the 10x Engineer
5. The Battle-Ready Engineer
6. Brilliant Idea
7. Pattern Matching
9. 1. Problem Solving a. CS Fundamentals b. Data Structures & Algorithms c. Patterns (e.g design patterns) d. Be Hands-on 2. Communication
10. What Are Data Structures
11. Data structures are ways of organizing and storing data in a computer program, given a desired use case. Common data structures include arrays, linked lists, stacks, queues, trees, and graphs.
12. Given a big bag containing books and fruits, how would you store them for safekeeping and easy access? You might put the fruits in a tray on the dining table, but the books will likely go on a shelf. Putting the fruits on a shelf is not ideal because they’d roll and fall off
13. In fact, for easy access, you might want to be deliberate on how you place the books on the shelf. E.g books should be standing, with their titles facing out
16. Some Simple Data Structures
17. Array Data Structure You just need a collection to store items
18. Linked List Data Structure You need a collection to store items but care about insertion order and being able to get the next item, given any item
19. Stack Data Structure You want a collection to store items but need the first item you can get out to be the last item you put in
20. You want a collection to store items but need the items to conform to / represent a hierarchy like in an org chart
21. What Are Algorithms
22. Algorithms are sets of steps for solving problems. Basic algorithms include those for sorting and searching.
23. Clear steps for cooking Nigerian Jollof, such that the outcome is deterministic and can be followed by anyone. Its gotta have clear measurements. You can’t just sprinkle salt “as the spirit leads”. The next person trying that approach might end up adding too much salt you know! Clear steps to land a US tech job. Clear steps to marry a baddie. Clear steps to search for a student with matric number ENG06768903 or a Nigerian with NIN of 45793023740374
24. How Do We Build Algorithms
25. 1. State the required input(s) 2. State any conditions (e.g type of data, does the data needs to be sorted? e.t.c) 3. Implement the steps 4. Determine and improve the time and space complexity (a.k.a its performance from a compute time & storage perspective. 5. Return the output 6. Communicate (4) with Big-O notation
26. How Do We Communicate About Algorithms
27. The Big(O) Notation is a fundamental concept to help us measure the time complexity and space complexity of the algorithm. In other words, it helps us measure how performant and how much storage and computer resources an algorithm uses.
29. Applying Algorithms To The Everyday Problem Of Search
30. This JavaScript code is trying to find the first number in the list of numbers, that is larger than 10
33. Linear search can be like my kids when we are driving to the playground. We basically just left the parking lot of our home and they’ll start asking “daddy are we there yet” until we get there, and by that time I am already mentally drained from having to respond to them every minute.
34. Binary Search Algorithm
35. Binary Search Algorithm
36. Linear search. Done In 7 Steps. Has O(n) performance which is linearly affected as the input data increases Binary search. Done In 3 Steps. Has O(logN) performance & is NOT linearly affected as the input data increases VS
37. VS About driving my kids to the playground, I think they later swapped out their “asking algorithm” from linear to binary, as they grew older. Instead of asking “daddy are we there yet” every minute, they now use visual cues (e.g landmarks along the way) to tell if we are heading in the right direction and how close we are. They’d only ask a couple of times (e.g if they think the traffic lights are slowing us down)
38. For a 1000-element array, in the worst case, linear search would take 1000 iterations to find the target or determine it's not present. In binary search on the other hand, the number of iterations will be determined by log₂(n), where n is the number of elements in the array ⇒ log₂(1000) ≈ 9.96. So, in the worst-case scenario, binary search would take approximately only 10 iterations to find the target or determine it's not present. Binary Search vs Linear Search Algo
39. In summary, for a 1000-element array: 1. Linear search would take up to 1000 iterations in the worst case scenario. 2. Binary search would take up to 10 iterations in the worst case scenario. Binary search is significantly more efficient, especially for large datasets, due to its logarithmic time complexity (performance relative to data size) compared to the linear time complexity of linear search. Binary Search vs Linear Search Algo
42. Demo Time Demo Repository Link : https://github.com/chalu/use-binary-search
44. Given 15,000 UNILAG-like matric numbers, search for one of them using binary search. Just for demo sake, imagine an Admin searching for an alumni in the web portal for a highly populated Uni. Ignore DBs for now!
46. Go to below link if demo video won’t play https://youtu.be/WRqbrPPQ9DU
47. Questions ?
48. Thank You @chaluwa linkedin.com/in/charlesodili