/Summer_Program_Python_Basic

Summer program: Python basic - search/sorting algorithm

The aim of this project is to let a high school student to get the basic knowledge of programming. Python is the best language for a starter to learn how to do programming.
The search and sorting algorithms are the most important algorithms in the computer science world. Even for engineers who have been worked for years, they would be asked to implement the search and sorting algorithms on the whiteboard in a limited time.

Learning Goals

  1. Learn the basic concepts of programming, such as variable, if-else, loop, input and output, recursive function.
  2. Learn the basic data structures in Python, such as list, dict and tuple.
  3. Learn the search algorithms (linear search and binary search), learn the sorting algorithms (bubble sort, mearge sort and quick sort).
  4. Learn Python decorater, use timeit decorater to profile the function execution time.
  5. Get the notion of algorithm complexity.

Expected Result

  1. Write a function to find an element in an array, e.g., given an array [1 ,2 ,3, 4, 5], we want to find 4, then return the index of 4, which should be 3 (In the computer world, the indexs are always counted from 0).
  2. Optimize the algorithm, to implement the binary search algorithm.
  3. Output the efficiency on the screen, tell the time it spends to do linear search and binary search.
  4. Learn how to write a recursive function (Please search the Fibonacci problem in Python, and think about is there any better way to solve the Fibonacci problem more quickly?)
  5. Learn about 3 sorting algorithms, bubble, quick and merge sort, and implement them.
  6. Use python decorater to profile the sorting functions.

References (not limited to these)

  1. https://www.jetbrains.com/pycharm/download/#section=mac
  2. https://wiki.python.org/moin/BeginnersGuide/Overview
  3. https://wiki.python.org/moin/SimplePrograms
  4. https://www.youtube.com/playlist?list=PLboXykqtm8dy_DNg1NZiS08Dnyj35PWXw
  5. https://stackoverflow.com/questions/700241/what-is-the-difference-between-linear-search-and-binary-search
  6. https://docs.python.org/3/library/timeit.html
  7. https://brew.sh
  8. Please search for sorting algorithm, recursive function, Python profier, etc.
Please notice: a good programmer can know every thing when he/she has the Internet access, please go to search anything you want to know by Google.

Timeline

Week1: Install the python IDE, learn the basic concepts about what is programming, how to run a programme. Learn the basic concepts about data structures, and implement the linear search algorithm.

Week2: Learn the binary search algorithm, implement it, and try to generate a long random array, compare the excecution time and think about: what is the prerequisit for conducting a binary search?

Week3: Learn about the sorting algorithm, and the recursive functions, implement the sorting algorithms.

Week4: Continue to implement the sorting algorithm, learn how to debug by PyCharm if meeting any bug. Finally show the sorting functions, and generate different length of arrays to test the efficiency, the result should be human-readable。