Computational Geometry: mudanças entre as edições
De Pontão Nós Digitais
Ir para navegaçãoIr para pesquisar
(13 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
Linha 1: | Linha 1: | ||
= ////////// Under Construction ////////// = | = ////////// Under Construction ////////// = | ||
This is the main page of a graduate level course | [[Arquivo:Computational-geometry-concept-diagram.png|500px|center]] | ||
This is the main page of a graduate level course in computational geometry being taught in 2019/2 at the Polytechnic Institute [http://pt.wikipedia.org/wiki/IPRJ IPRJ]/UERJ. It is generally useful for programmers at the advanced level in the fields of machine learning, scientific simulations, graphics, computer vision and and multimedia programming. | |||
== General Info == | |||
* Instructor: prof. [http://rfabbri.github.io Ricardo Fabbri], Ph.D. Brown University | |||
* Meeting times: Wednesdays 7:50-11:30, Thursdays 7:50-9:40, and 15:00-17:00, room 110. | |||
* Evaluation criteria: at least 2 quizzes (40%), practical projects (60%). | |||
* Forum for file exchange and discussion: email and IRC #labmacambira | |||
== Lecture Log == | == Lecture Log == | ||
Linha 43: | Linha 54: | ||
* Sort building blocks | * Sort building blocks | ||
==== | ==== Wed 30Out19 ==== | ||
* Overdue: Vertical Function graph (K&H Histogram) | * Overdue: Vertical Function graph (K&H Histogram) | ||
* Due: Insert on sorted array | * Due: Insert on sorted array (Juliana: 9,5) | ||
* Due: Merge two sorted arrays as warmup for next lecture | * Due: Merge two sorted arrays as warmup for next lecture (Juliana: 5) | ||
* Due: Simple sort by recursive and non-recursive max is stable? argue in PDF | * Due: Simple sort by recursive and non-recursive max is stable? argue in PDF (Juliana 0) | ||
* Content | |||
** Reviewed due homework | |||
** Pointers, references | |||
** Arrays and pointers | |||
** Matrices as multidimensional arrays. Pointers. | |||
** Malloc for arrays and matrices | |||
** Structs | |||
** Void * | |||
** Pointers to functions | |||
==== Thu 31Out19 ==== | |||
* Due: better sorted insert | |||
* Due: max() in vertical histogram | |||
* Due: more efficient merge | |||
* Bitwise operators. Modulo operator. | |||
* Excercises: one regarding Matrices, another regarding number and bit manipulation. | |||
* Image lookup table for sorting intensities | |||
==== Wed 13Out19 ==== | |||
* Exam: programming fundamentals | |||
==== Future ==== | ==== Future ==== | ||
Linha 78: | Linha 108: | ||
Dados 2 vetores de inteiros A=[a1,a2,a3] e B=[b1,b2,b3] : | Dados 2 vetores de inteiros A=[a1,a2,a3] e B=[b1,b2,b3] : | ||
# Crie uma função que leia estes vetores do teclado | |||
# Crie um função que calcule o produto escalar entre estes vetores. | |||
# Crie uma função que calcule o produto vetorial entre estes vetores. | |||
produto escalar C = A*B=a1b1 + a2b2 + a3b3 | # Crie uma função que imprima o resultado na tela | ||
produtor vetorial C =[a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1] | :produto escalar <code>C = A*B=a1b1 + a2b2 + a3b3</code> | ||
:produtor vetorial <code>C =[a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1]</code> | |||
Linha 90: | Linha 121: | ||
*** partition an arbitrary array into smaller and larger than a given t | *** partition an arbitrary array into smaller and larger than a given t | ||
==== Tarefa 7 - Busca Binaria 30Mai19 ==== | ==== Tarefa 7 - Busca Binaria 30Mai19 ==== | ||
Linha 106: | Linha 131: | ||
* Implementar o mergesort, o quicksort e o insertion sort | * Implementar o mergesort, o quicksort e o insertion sort | ||
=== Part 2: Computational Geometry problems to practice C++ programming === | |||
*** Compute scalar and vector product of 3-vectors | |||
*** Hash tables, Buckets for point query | |||
*** Proximity | |||
*** Voronoi Diagrams | |||
*** Curve Algorithms | |||
===== Homework: given a list of points, compute the closest point ===== | |||
* Naive algorithm | |||
* Hash table from Programming Pearls | |||
===== Homework: given a list of points, output all lines passing through each pair of points ===== | |||
* Line going through two points | |||
==== Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA) ==== | ==== Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA) ==== | ||
Linha 142: | Linha 182: | ||
*** | *** | ||
[[Category:Lab Macambira]] [[Category:IPRJ]] | [[Category:Lab Macambira]] [[Category:IPRJ]] |
Edição atual tal como às 10h58min de 31 de outubro de 2019
////////// Under Construction //////////
This is the main page of a graduate level course in computational geometry being taught in 2019/2 at the Polytechnic Institute IPRJ/UERJ. It is generally useful for programmers at the advanced level in the fields of machine learning, scientific simulations, graphics, computer vision and and multimedia programming.
General Info
- Instructor: prof. Ricardo Fabbri, Ph.D. Brown University
- Meeting times: Wednesdays 7:50-11:30, Thursdays 7:50-9:40, and 15:00-17:00, room 110.
- Evaluation criteria: at least 2 quizzes (40%), practical projects (60%).
- Forum for file exchange and discussion: email and IRC #labmacambira
Lecture Log
Part 1: C++ Programming Practice and Review
Wed 9Out19 (twice lecture load)
- Hello world
- for loop print 10x
- Slides 1 Review C Fabbri
- Variables, arrays/vectors
- Farenheit to/from celcius program: homework
Wed 16Oct19
- Show results of Farenheit to Celsius
- Learn Codeblocks
Thu 17Oct19
- Print function graph (K&R Histogram)
- Horizontal
- Learn how to write max function: non-recursive and recursive
- Learn first simple sort algorithm using max
- Horizontal
Wed 23Out19 (twice lecture load)
- Due: simple sort using max
- bucket sort (class exercise). Due. (student juliana: done)
- Other simple sorts. Insertion, selection, bubble
- Basic building block: insert on sorted array, keeping it sorted
- Theory: arrays.
Thu 24Out19
- Overdue: simple sort using max
- Did: used max function
- at first, max function without index
- Sub-exercise: implement max of an array to return index, recursive and non-recursive
- did: sort with max function, with index
- at first, max function without index
- Question: does it work with repeated entries?
- If you have a vector of float height[num_people] and age[num_people], and there is a repeated age, can you print ages and respective heights sorted by age, without losing information?
- What is a stable sort
- Did: used max function
- Vector and cross product exercise
- Exercise from qualify
- Sort building blocks
Wed 30Out19
- Overdue: Vertical Function graph (K&H Histogram)
- Due: Insert on sorted array (Juliana: 9,5)
- Due: Merge two sorted arrays as warmup for next lecture (Juliana: 5)
- Due: Simple sort by recursive and non-recursive max is stable? argue in PDF (Juliana 0)
- Content
- Reviewed due homework
- Pointers, references
- Arrays and pointers
- Matrices as multidimensional arrays. Pointers.
- Malloc for arrays and matrices
- Structs
- Void *
- Pointers to functions
Thu 31Out19
- Due: better sorted insert
- Due: max() in vertical histogram
- Due: more efficient merge
- Bitwise operators. Modulo operator.
- Excercises: one regarding Matrices, another regarding number and bit manipulation.
- Image lookup table for sorting intensities
Wed 13Out19
- Exam: programming fundamentals
Future
- Intro to advanced sorts: Merge sort, Quick Sort
- Basic building blocks:
- merge: merge two sorted arrays into a sorted array.
- partition an arbitrary array into smaller and larger than a given t
- Basic building blocks:
Tasks + Homework
Part 1: C++ Programming practice and Review
Hello World
Celsius to/from Farenheit
Print Function graph (K&R Histogram): horizontally
- Sub exercise: max function
Implement max function recursively
Sort using max function
Print Function graph (K&R Histogram): vertically
Bucket sort
Vector and cross product exercise
- Exercise from qualify
Dados 2 vetores de inteiros A=[a1,a2,a3] e B=[b1,b2,b3] :
- Crie uma função que leia estes vetores do teclado
- Crie um função que calcule o produto escalar entre estes vetores.
- Crie uma função que calcule o produto vetorial entre estes vetores.
- Crie uma função que imprima o resultado na tela
- produto escalar
C = A*B=a1b1 + a2b2 + a3b3
- produtor vetorial
C =[a2b3 – a3b2, a3b1 – a1b3, a1b2 - a2b1]
Basic sort building blocks
- insert: insert on sorted array, keeping it sorted
- merge: merge two sorted arrays into a sorted array.
- partition an arbitrary array into smaller and larger than a given t
Tarefa 7 - Busca Binaria 30Mai19
- Implementar busca binaria de um vetor ordenado de floats
- Utilizar apenas linguagem C e sua propria implementacao
- Bonus: implementar em C++ usando a biblioteca padrao
Tarefa 8 - Ordenacao 6Jun19
- Implementar o mergesort, o quicksort e o insertion sort
Part 2: Computational Geometry problems to practice C++ programming
- Compute scalar and vector product of 3-vectors
- Hash tables, Buckets for point query
- Proximity
- Voronoi Diagrams
- Curve Algorithms
Homework: given a list of points, compute the closest point
- Naive algorithm
- Hash table from Programming Pearls
Homework: given a list of points, output all lines passing through each pair of points
- Line going through two points
Trabalho: Parte 1 valendo bonus, dia 2/Maio/2019, Parte2 completo 16/Maio/2019 (REMARCADA)
- Dado um labirinto na forma de uma matriz, onde os caminhos sao formados por espaco ' ',
e as paredes do labirindo sao formadas pela letra 'a' ou '8' conforme abaixo, e dada uma entrada e uma saida marcadas por espaco ' ' ou na parede de cima do labirinto, ou na parede de baixo, resolva o labirinto ou retorne 0 caso nao exista um caminho. Note que tanto as paredes ou os caminhos podem ter largura maior que 1 caractere.
- A parte 2 do trabalho valera nota e devera ser entregue 1 semana apos a parte 1. A parte 1 eh apenas bonus para incentivar o aluno a resolver o problema com ideias proprias.
- Sera dado um grande bonus.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a 8 8 8 8 8 8 8 8 8 aaaaaaaaa 8 aaaaa aaaa8aaaa aaaa8 aaaaa aaaaa 8 8 8 8 8 8 8 8 8 8 8 8 8aaaaaaaa a 8aaaaaaa8 8aaaaaaaa 8aaaa a 8 8 8aaaaaaa8 8 8 8 8 8 8 8 8 8 8 8 8 8 a 8aaa8aaaaaaaa a 8 aaaaaaaa8 8aaa8 8 8aaaaaaaa 8 8 8 8 8 8 8 8 8 8 8 8 8 8aaaaaaaaaaaa 8aaa8 8aaaa 8 aaaaa 8aaaaaaaa 8 aaaa8 8 8 8 8 8 8 8 8 8 8 8 8 aaaaa 8aaaa 8 8aaaa 8 8aaaaaaa8 a a 8 8aaaaaaaaaaa8 8 8 8 8 8 8 8 8 8 8 8 8 8aaaaaaa8aaaa 8 8 8 aaaa8aaaa 8 aaaa8 8 8aaaa 8aaaa 8 8 8 8 8 8 8 8 8 8 8 8 aaaaa 8 8aaaaaaaa 8aaaa 8 8aaaa 8aaa8 aaaa8aaaaaaaa 8 8 8 8 8 8 8 8 8 8 8 8 8 aaaa8aaaa a 8aaaa aaaa8aaaa 8 8 8aaaaaaaaaaaa 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8aaaaaaaa 8 8 8 8aaa8 8aaaaaaa8 aaaaaaaaa 8 8aaaaaaa8 8 8 8 8 8 8 8 8 8 8 8 8 aaaa8 8aaa8 aaaaa 8aaaaaaaa 8aaa8 a 8aaaaaaaa a 8 8 8 8 8 8 8 8 8 8aaaaaaaaaaaaaaaaaaa8aaaaaaaaaaa8aaaaaaaaaaaaaaa8aaaaaaaaaaaaaaa8aaa8