Data Structures & Algorithms Guide
Uploaded by
yousef shabanData Structures & Algorithms Guide
Uploaded by
yousef shabanBaghdad >> KMR >> Arabic competitive Course
OpenDSA
Codes GitHub >> Folk
2-Big-O Notation
How to implement DS on Worst Case scenario move from worst level to best level
Try to reduce complexity from n square >>> n or anything better than before
How to implement code on worst case scenario
Space and Time Complexity
Worst case >> that is High n
Subroutine >> take n as for loop
هيكلية المصفوفات ||3- Array Structure
C >> to add N >> movement process on array ( insert process ) O(n)
Delete >> take constant time but movement process for each element take n Times
Space O(n) based on size we define it
Java >> ArrayList
4- Implement Array in Java
Array of object
هيكلية المصفوفات ||5- Dynamic Array Structure
ديناميكية
New array size
Every time when need to add new element in last not enough size >> we will double size of array
6- implement dynamic array in java
7- Linked List Structure|| هيكلية لنك لست
عندم يكون لديك حجم محدد من زاكرة يفضل استدخماها على االراي
2 > 3 > then use 4 and so on
Array more faster access for a lot access process prefer array
More a lots from Add delete process prefer to use link list instead array
8- implement Linked list in java
9- Stack Structure|| شرح
LIFO
When add reach stack is fill
Need insert & delete >> Stack not access & Search
10- implement Stack in Java
StackArrayDynamic
Stack >> Link list
11- Queue Structure|| شرح
FIFO
Fist check if Quereu is full
Queue with link list most used
Queue similar with stack but different on the below
12- implement Queue in Java
Remember problem last lecture >> Rear and Front
Important notes:
Say your queue is full ( problem ) استخدام الراي في تنفيذ القيو
13- Linked List Queue Structure|| شرح
احدى الحلول لمشكلة كيو از فل
Sizeهنا ال يوجد لديك اي مشكلة Rفي
14- implement queue use Linked List in
Java
Homework
15- Hash Table Structure || شرح
Wekibidia how to save 20 topics >> Iraq history
Important to clarify Hash idea
Faster Search based on index for all link list
Aim >> Searching more Faster for your target
16- Implement Hash-Table in Java
Link list
17- Refresh Collections|| ادوات جاهزة في هيكلة
البيانات
Collections library on Java ( ready used )
18- Linear Search Algorithm|| خوارزمية البحث
We need better search algorithm instead of linear (Big O(n)) >> Log n >> O (1)
19- Linear Search implementation in Java
لمن البيناتا تضاعف عندك بسموLog
Log >> Double divide middle
Divide for mid >> Log n
21- Binary Search implementation in Java
بعد كم محاولة لقاه بعد 19محاولة تنفيذ
999999 >> 19 Trials Binary instead linear
خوارزمية||22- Interpolation Search Algorithm
البحث
مفش داعي تبحث في البيانات الي بتبدا في 00وانت تريد ان تبحث عن 11
Then maybe to apply Binear Search to divide more access
23- Interpolation Search implementation in
Java
99999 linear >> 20 times Binary >> 1 interpolation due to search nearly unique not similarity with
others
24- Recursion calls- االستدعاء الذاتي
Stackوبصير يسحب البيانات من
بعد ما عالجها كلها يخرجها كلها من لستاك
خوارزمية الترتيب || 25- Bubble sort Algorithm
بقارن كل عنصر مع اللي بعده
If 8 > 4 then replace
اكبر رقم في اول عملية ينتقل الى نهاية
Then repeat process again from first
تاني اكبر رقم اصبح في نهاية
27 - Merge sort Algorithm|| خوارزمية الترتيب
28- Merge Sort implementation in Java
Important Code to implement
29- Heap sort Algorithm|| خوارزمية الترتيب
Heap >> convert Tree to Array
Heap find >> work compare from under Tree to above is larger then move number
Became Larger number on Root >> Put on last position number inside array
Get out >> put on last Tree and so on ( n times ) Tree ( Log n )
Q(n Log n)
) Space O(1كل هادي عملية حتم داخل االراي محددة مش حتوخد مساحة تانيه علشان هيك
Very important compare merge with Heap
30- implement Heap Sort in Java
Very important Code to implement
31- quick sort Algorithm|| خوارزمية الترتيب
Right > pivot and left < Pivot then replace between them >> So on
Then divide it for two array then choose two pivot
Problem when choose pivot always right > Pivot and left < pivot >> Without any divide remain as it
Problem >> when pivot nor change >> remain on the same place
Summary all Search algorithms >> Heap Sort is the best
32- Quick Sort implementation in Java
33- Binary Tree algorithm|| شجرة باينري
Graph theory >> افضل وسيلة لتمثيل المشاكل وحلها
Binary Tree >> اقصى شي نود تحتوي على اتنين تشايلد
طريقة تمضثيل بالكود
Double link list >> in last Tree >> Null
جانب االيمن من النود كله يكون اكبرمنو وهكذا وجانب االيسر اصغر
Search 11 >> Faster >> Compare on each node this is greater or smaller
بدي ابحث عن المكان اللي بدي اتواجد فيه >> Add 14
Each node >> Compare > or <
Delete
If have two child >> node that delete ( important note ) >> Delete 13
We need to remove node 12 >> Becode node 10 >> more than two child >> Problems Appear
34- Binary tree implementation in Java
Important define instances
35- Graph Representation with Matrix vs
Adjacency list|| تمثيل البيانات
Direction Graph >> باتجاه واحد
Adjacency list >> Array with link List
36- Depth First Search(DFS) || تصفح االشجار
Go to (Lowest ) >> non-return for past if reach end then backtrack (remove from stack) does not need
from search process
زار االولى وتانية خلص بروح على اللي ضايله
37- DFS implementation in Java(Very
important Code)
Using Adj-List (array with link list)
38- Breadth First Search (BFS) || تصفح
االشجار
Differ used Queue while Depth used Stack
Cursor (Front) after remove A on B >> what is Child of B ?
Then repeat process for C ?
Breadth بحث افقيا وليس عموديا
What is child of A >> when move Front
39- BFS implementation in Java
40- Nearest Neighbor and Shortest path
Conditions >> Connected, non-Circle
وفرت 26متر
Connected non-circles
41- Dijkstra's Algorithm || خوارزمية
Find short path
Between City >> inside Network
Node that was visited >> not need to calculate your cost
Problem >> explore all Nodes (Cost)
42- A* Algorithm || خوارزمية
Heuristicممكن القيمة تعمل ولكن ليس في جميع الحاالت هذا معنى
هي تكلفة الحقيقية )G(n
H(n) Heuristic value
)Note compare F(n) Value so 8 > 7 >> Go to (7
Second way: Priority Queue
بتجيب المسار اللي بعجه وبتقارن داخل الكيو مني اقل وهيك وبعدين بمسحها Rوهكذا
وبعدين بتحط في الكيو جميع المسارات للنقط اللي رايح عليها بتجيب كل اللي متصالت في ااه
امسحها وخدها بلاير كوست
مفهوم البرمجة ||43- Dynamic Programming
الديناميكية
A lot of recursions will be done >> Large problem
ما زال الحلول ابتتكرر وما زال المشكلة بتتكرر حاول اختزل عملك
44- Dynamic Programming- edit distance||
كيف يعرف كوكل بماذا تفكر
نبحث عن العمليات المتشابهة واللمتكررة
توجد عمليات تكرر اكثر من مرة
علشان احول كلمة كات ل دوق محتاج اغير 3احرف يعني تكلفة3
هنا تكلفة تغيير حرفين
مشاكل اليمكن حلها ||45- NP Complete problem
قد تفقد وظيفتك بسببها
وال يستطيع شخص اخر على حلها
Travel Salesman
وال وحدا منهم تسطيع حل المشكلة
كيف بدي اعرف انو المشكلة ال يمكن حلها
لمن يكون االنبت غير متناسق مع االوت بوت
46- Knapsack problem HW|| واجب سارق
المتجر
?كيف كانت مقابلتي مع كوكل وماهي االسئلة 47-
حل سؤال االول Linklist Stack
Team 2: Cities
Depth first Search solution used Back-Tracking
Team 3 >> Hash_Map
Team 4 : Binary Tree >> Two Equally Tree
Team 5 :
Draw Triangle >> Cover all Triangles
