Algorithms and data structure introduction

Algorithms and data structure introduction

1. M269 Algorithms, Data Structures and Computability By: Dr. Ahmed Gawish [email protected] Lec 1. Course Intro Spring 2018

2. Agenda What does this course talk about? Why do we need this course? Jobs in the market related to this course. What are we going to learn in this course. Course plan and calendar. Assessment map. How to study this course to get A+ Resources for self-learning. Your first task for the next week.

3. D esign algorithms that are correct and efficient Our goal:

4. Why to learn algorithms ? http ://www.neatorama.com/twaggies/2010/11/07/no-112-robcorddry/

5. Sorting algorithm Dijkstra’s algorithm Floyd’s algorithm Kruskal’s algorithm Design methods: Backtracking = Forbidden  Greedy Design by Induction Divide and Conquer Dynamic Programming Searching algorithm KMP algorithm

6. Course Goals Learn to design algorithms that are correct and efficient How do we know that: an algorithm is correct ? -> correctness proofs an algorithm is efficient ? -> analysis of algorithms (time complexity) How to design solutions for new problems ? Learning general techniques for design Studying a set of well-known algorithms, to serve as examples of success stories for applying general design techniques Become aware that good algorithms are key parts of software engineering practice !

7. What does this course talk about? Data Structure: Queue, Stack, Linked-list, Tree, Heap, Hash-table. Algorithms: Sorting , Searching, Pattern Matching, Graph. Paradigms: Divide and Concorde, Optimization, Dynamic, Greedy, Brute-force, Recursion. Complexity: Complexity analysis and big  notation. Sets and Logic: Sets and Predicate logic. Computability: Computation and its limits. All of these will be implemented with Python

8. M269 ... Why? One of the basic pillars of advanced computing projects consists of the set of proper algorithms used to solve not only traditional but also unconventional IT problems. With the huge amount of data embedding the new data science, being skilled in setting proper data structure , managing and understanding computability techniques become a must nowadays. M269 is one of the most important modules for information technologies and computing related majors and tracks . The underlying concepts of this module are implemented using the python programming language. Source : M269 course specs

9. Aims Provide the students with the required skills to possess the computational thinking. These skills start by proper understanding and analyzing the problems to be solved and end by providing computer programs that solve these problems. One of the important aspects of this module is to provide the students with the awareness of the limits of computation and the ability to decide which problems can and which cannot be solved efficiently with computers. Source : M269 course specs M269 ..Aims

10. Jobs in the Market & Average Salary

11. http://www.businessinsider.com/skills-that-can-get-you-hired-in-us-2016-11

12. Why Python?

13. 2013 2015 2017 Why Python? Comparison with other programming languages The future will be Python

14. Why Python? Jobs in the market the need Python skills

15. The course content Introduction From problems to programs Sorting Searching Optimization Sets, logic and databases The limits of computation

16. The course content 1- Introduction Introduction What is computation? Introducing Python Introduction Come fly with Python Basic Python Why Python? Computational thinking 2- From problems to programs From problem to program Getting the inputs and outputs Getting the algorithm Getting the ADT A taste of formal logic Iteration and logic Pre- and post-conditions Correctness and clarity Getting data structures right How do we know it is right? Dividing and conquering

17. The course content 3-Sorting What is sorting? Naive sorting Bubble sort Selection sort Insertion sort Complexity of straight sorting algorithms Inducing, reducing and recusing Induction Reduction and recursion Recursive sorting Sorting smart Dividing and conquering Trees and heaps Sorting – two final thoughts 4- Searching Searching lists Searching for patterns Basic string search The quick search algorithm The Knuth–Morris–Pratt algorithm Other Maps algorithms Hashing and hash tables Search trees Binary search trees AVL trees

18. The course content 5- Optimisation Optimization Graphs and greed Dynamic programming 6- Sets, logic and databases Sets and propositional logic Predicate logic, or first order logic Database retrieval using simple queries The cardinality of infinite sets 7-The limits of computation Computability Logic revisited Computational complexity Physics and computing

19. The Assessment of the Course Types and Nature: TMA: 20% Nature: Solving coding problems with report. MTA: 30% Nature: MCQ, Short questions, Coding Final: 50% Nature: MCQ, Short questions, Coding Time: Due dates according to the academic calendar

20. Basic info about the course This module is a core one that is offered in 4 tracks: WD , CS , ITC and CwB . Prerequisites: Studying this module requires a certain basic knowledge in programming and maths. Pre-requisites are TM105 & MT131 It is a prerequisite for the following course MT372 - Parallel Computing TM351 - Data Management and Analysis TM366 - Artificial Intelligence Module title M269: Algorithms, Data structures and Computability. Level 2 Module tutor TBA Credit value 30 Module type Taught Notional learning hours 8

21. Text Books

22. Important Dates Spring 2018

23. How to study this course to get A+: Focus during the lecture and write down your questions. Don’t leave anything without understanding it. For each data structure understand the following: Its Abstract Data Representation. How it will be stored in the computer’s memory (Physically). Its operations (insert, remove, retrieve, update). Implement it using Python. For each algorithm understand the following: It’s runtime complexity. It’s space complexity. How it works. It’s paradigm. It’s input and output. Implement it using Python. Use the self-learning resources. Master the Python 3 programming language.

24. Resources for self-learning: Online Python Visualization tool: http://www.pythontutor.com/visualize.html#mode=edit Python algorithms visualization (Web Animations): https://pyalgoviz.appspot.com/ https://visualgo.net/en YouTube Data structures and Algorithms tutorials: https://www.youtube.com/watch?v=92S4zgXN17o&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P https://www.youtube.com/watch?v=c1IW9S2bR2w&list=PLib7LoYR5PuDxi8TxxGKxMgf8b-jtoS3i https://www.youtube.com/watch?v=Nkw6Jg_Gi4w&list=PLj8W7XIvO93rJHSYzkk7CgfiLQRUEC2Sq Geeksforgeeks Website: http://www.geeksforgeeks.org/python/ http://www.geeksforgeeks.org/data-structures/ http://www.geeksforgeeks.org/fundamentals-of-algorithms/ . Python 3 tutorials: http://python-course.eu/python3_course.php https://www.youtube.com/watch?v=P74JAYCD45A&list=PLGzru6ACxEALhcvY18A-iox-mEoieHMVG https://www.youtube.com/watch?v=HBxCHonP6Ro&list=PL6gx4Cwl9DGAcbMi1sH6oAMk4JHw91mC_

25. Your first task for the next week Python 3 tutorials: http://python-course.eu/python3_course.php https://www.youtube.com/watch?v=P74JAYCD45A&list=PLGzru6ACxEALhcvY18A-iox-mEoieHMVG https://www.youtube.com/watch?v=HBxCHonP6Ro&list=PL6gx4Cwl9DGAcbMi1sH6oAMk4JHw91mC_ “Learn/Revise Python 3” Any Questions? Thank you