Anki Deck Changes

Commit: fc3baa4d - simplify ADT cards and fix master theorem

Author: obrhubr <obrhubr@gmail.com>

Date: 2025-12-26T15:06:46+01:00

Changes: 6 note(s) changed (0 added, 6 modified, 0 deleted)

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: Ah6X9iA&#j
modified

Before

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::4._Stack
The ADT stack has the following operations:
  •  push(k, S): push a new object k to the top of the stack S
  •  pop(S): remove and return the top element of the stack S
  •  top(S): get the top element of the stack S without deleting it

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::4._Stack
The ADT stack has the following operations:
  •  push(k, S): push a new object k to the top of the stack S
  •  pop(S): remove and return the top element of the stack S
  •  top(S): get the top element of the stack S without deleting it
Other operations might be isEmpty or emptystack which produces and emtpy stack.

After

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::4._Stack
The ADT stack has the following operations:
  • push(k, S): push a new object k to the top of the stack S
  • pop(S): remove and return the top element of the stack S
  • top(S): get the top element of the stack S without deleting it

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::4._Stack
The ADT stack has the following operations:
  • push(k, S): push a new object k to the top of the stack S
  • pop(S): remove and return the top element of the stack S
  • top(S): get the top element of the stack S without deleting it
Other operations might be isEmpty or emptystack which produces and emtpy stack.
Field-by-field Comparison
Field Before After
Text The ADT&nbsp;<b>stack</b>&nbsp;has the following operations:<br><ul><li>{{c1::&nbsp;<b>push(k, S)</b>}}: {{c2:: push a new object&nbsp;<b>k</b>&nbsp;to the top of the stack&nbsp;<b>S</b>}}</li><li>{{c3::&nbsp;<b>pop(S)</b>}}: {{c4:: remove and return the top element of the stack&nbsp;<b>S</b>}}</li><li>{{c5::&nbsp;<b>top(S)</b>}}: {{c6:: get the top element of the stack&nbsp;<b>S</b>&nbsp;without deleting it}}</li></ul> The ADT&nbsp;<b>stack</b>&nbsp;has the following operations:<br><ul><li><b>push(k, S)</b>: {{c1:: push a new object&nbsp;<b>k</b>&nbsp;to the top of the stack&nbsp;<b>S</b>}}</li><li><b>pop(S)</b>: {{c2:: remove and return the top element of the stack&nbsp;<b>S</b>}}</li><li><b>top(S)</b>: {{c3:: get the top element of the stack&nbsp;<b>S</b>&nbsp;without deleting it}}</li></ul>
Tags: ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::4._Stack

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: D2>~h
modified

Before

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::5._Queue
The ADT quue has the following operations:
  •  enqueue(k, S): append at the end of the queue
  •  dequeue(S): remove and return the first element of the queue

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::5._Queue
The ADT quue has the following operations:
  •  enqueue(k, S): append at the end of the queue
  •  dequeue(S): remove and return the first element of the queue

After

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::5._Queue
The ADT quue has the following operations:
  • enqueue(k, S): append at the end of the queue
  • dequeue(S): remove and return the first element of the queue

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::5._Queue
The ADT quue has the following operations:
  • enqueue(k, S): append at the end of the queue
  • dequeue(S): remove and return the first element of the queue
Field-by-field Comparison
Field Before After
Text The ADT&nbsp;<b>quue</b>&nbsp;has the following operations:<br><ul><li>{{c1::&nbsp;<b>enqueue(k, S)</b>}}: {{c2:: append at the end of the queue}}</li><li>{{c3::&nbsp;<b>dequeue(S)</b>}}: {{c4:: remove and return the first element of the queue}}</li></ul> The ADT&nbsp;<b>quue</b>&nbsp;has the following operations:<br><ul><li><b>enqueue(k, S)</b>: {{c2:: append at the end of the queue}}</li><li><b>dequeue(S)</b>: {{c4:: remove and return the first element of the queue}}</li></ul>
Tags: ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::5._Queue

Note 3: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: F*Z7jn}vxk
modified

Before

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List
The ADT List defines the following operations:
  •  insert(k, L): insert the key K at the end of the list L
  •  get(i, L): return the memory address of the i-th key in list L
  •  delete(k, L): remove the key k from the list L
  • insertAfter(k, k', L): inserts the key k' after the key k in the list L

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List
The ADT List defines the following operations:
  •  insert(k, L): insert the key K at the end of the list L
  •  get(i, L): return the memory address of the i-th key in list L
  •  delete(k, L): remove the key k from the list L
  • insertAfter(k, k', L): inserts the key k' after the key k in the list L

After

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List
The ADT List defines the following operations:
  • insert(k, L): insert the key K at the end of the list L
  • get(i, L): return the memory address of the i-th key in list L
  • delete(k, L): remove the key k from the list L
  • insertAfter(k, k', L): inserts the key k' after the key k in the list L

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List
The ADT List defines the following operations:
  • insert(k, L): insert the key K at the end of the list L
  • get(i, L): return the memory address of the i-th key in list L
  • delete(k, L): remove the key k from the list L
  • insertAfter(k, k', L): inserts the key k' after the key k in the list L
Field-by-field Comparison
Field Before After
Text The ADT <b>List</b> defines the following operations:<br><ul><li>{{c1::&nbsp;<b>insert(k, L)</b>}}: {{c2:: insert the key&nbsp;<b>K</b>&nbsp;at the end of the list&nbsp;<b>L</b>}}</li><li>{{c3::&nbsp;<b>get(i, L)</b>}}: {{c4:: return the memory address of the i-th key in list&nbsp;<b>L</b>}}</li><li>{{c5::&nbsp;<b>delete(k, L)</b>}}: {{c6:: remove the key <b>k</b>&nbsp;from the list&nbsp;<b>L</b>}}</li><li>{{c7::<b>insertAfter(k, k', L)</b>}}: {{c8:: inserts the key&nbsp;<b>k'</b>&nbsp;after the key&nbsp;<b>k</b>&nbsp;in the list&nbsp;<b>L</b>}}</li></ul> The ADT <b>List</b> defines the following operations:<br><ul><li><b>insert(k, L)</b>: {{c1:: insert the key&nbsp;<b>K</b>&nbsp;at the end of the list&nbsp;<b>L</b>}}</li><li><b>get(i, L)</b>: {{c2:: return the memory address of the i-th key in list&nbsp;<b>L</b>}}</li><li><b>delete(k, L)</b>: {{c3:: remove the key <b>k</b>&nbsp;from the list&nbsp;<b>L</b>}}</li><li><b>insertAfter(k, k', L)</b>: {{c4:: inserts the key&nbsp;<b>k'</b>&nbsp;after the key&nbsp;<b>k</b>&nbsp;in the list&nbsp;<b>L</b>}}</li></ul>
Tags: ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List

Note 4: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: Ld,vXkta~C
modified

Before

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::6._Priority_Queue
The ADT priorityQueue has the following operations:
  • insert: insert with priority p
  • extractMax: removes and returns element with highest priority.

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::6._Priority_Queue
The ADT priorityQueue has the following operations:
  • insert: insert with priority p
  • extractMax: removes and returns element with highest priority.

After

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::6._Priority_Queue
The ADT priorityQueue has the following operations:
  • insert: insert with priority p
  • extractMax: removes and returns element with highest priority.

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::6._Priority_Queue
The ADT priorityQueue has the following operations:
  • insert: insert with priority p
  • extractMax: removes and returns element with highest priority.
Field-by-field Comparison
Field Before After
Text The ADT <b>priorityQueue</b>&nbsp;has the following operations:<br><ul><li><b>{{c1:: insert}}</b>: {{c2::insert with priority&nbsp;<b>p}}</b><br></li><li><b>{{c3:: extractMax}}</b>: {{c4::removes and returns element with highest priority.}}<br></li></ul> The ADT <b>priorityQueue</b>&nbsp;has the following operations:<br><ul><li><b>insert</b>: {{c1::insert with priority&nbsp;<b>p}}</b><br></li><li><b>extractMax:</b>&nbsp;{{c2::removes and returns element with highest priority.}}<br></li></ul>
Tags: ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::6._Priority_Queue

Note 5: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: rp1#iPsvnq
modified

Before

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::2._Linked_List
In a linked list, the keys don't appear in order in memory. They each contain {c2::a pointer to the start of the next element in the list instead}}.

We also have an extra pointer to the end in practice.

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::2._Linked_List
In a linked list, the keys don't appear in order in memory. They each contain {c2::a pointer to the start of the next element in the list instead}}.

We also have an extra pointer to the end in practice.
The last pointer of the list is a null pointer to indicate the end.

After

Front

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::2._Linked_List
In a linked list, the keys don't appear in order in memory. They each contain a pointer to the start of the next element in the list instead.

We also have an extra pointer to the end in practice.

Back

ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::2._Linked_List
In a linked list, the keys don't appear in order in memory. They each contain a pointer to the start of the next element in the list instead.

We also have an extra pointer to the end in practice.
The last pointer of the list is a null pointer to indicate the end.
Field-by-field Comparison
Field Before After
Text In a <b>linked list</b>, the keys {{c1::don't appear in order in memory}}. They each contain {c2::a pointer to the start of the next element in the list instead}}.<br><br>We also have {{c3::an extra pointer to the end in practice}}. In a <b>linked list</b>, the keys {{c1::don't appear in order in memory}}. They each contain {{c2::a pointer to the start of the next element in the list instead}}.<br><br>We also have {{c3::an extra pointer to the end in practice}}.
Tags: ETH::1._Semester::A&D::05._Data_Structures::1._ADT_List::2._Linked_List

Note 6: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: uxhT]f%32k
modified

Before

Front

ETH::1._Semester::A&D::02._Asymptotic_Notation::3._O-Notation
Master Theorem: If  \(b = \log_2(a)\) then {{c2:: \(T(n) \leq O(n^{\log_2 a(=b)} \cdot \log n)\)}}.

Back

ETH::1._Semester::A&D::02._Asymptotic_Notation::3._O-Notation
Master Theorem: If  \(b = \log_2(a)\) then {{c2:: \(T(n) \leq O(n^{\log_2 a(=b)} \cdot \log n)\)}}.
The recursive and non-recursive work is balanced.

After

Front

ETH::1._Semester::A&D::02._Asymptotic_Notation::3._O-Notation
Master Theorem: If  \(b = \log_2(a)\) then {{c2:: \(T(n) \leq O(n^{\log_2 a} \cdot \log n)\)}}.

Back

ETH::1._Semester::A&D::02._Asymptotic_Notation::3._O-Notation
Master Theorem: If  \(b = \log_2(a)\) then {{c2:: \(T(n) \leq O(n^{\log_2 a} \cdot \log n)\)}}.
The recursive and non-recursive work is balanced.
Field-by-field Comparison
Field Before After
Text Master Theorem: If {{c1::&nbsp;\(b = \log_2(a)\)}} then {{c2::&nbsp;\(T(n) \leq O(n^{\log_2 a(=b)} \cdot \log n)\)}}. Master Theorem: If {{c1::&nbsp;\(b = \log_2(a)\)}} then {{c2::&nbsp;\(T(n) \leq O(n^{\log_2 a} \cdot \log n)\)}}.
Tags: ETH::1._Semester::A&D::02._Asymptotic_Notation::3._O-Notation
↑ Top